Fişierul intrare/ieşire:	obstacole.in, obstacole.out	Sursă	Junior Challenge 2019
Autor	Vlad Turcuman	Adăugată de	Junior Challenge 2019 •JuniorChallenge2019
Timp execuţie pe test	0.375 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Obstacole

Se dau N segmente în plan, neorizontale şi neverticale care nu se intersectează în niciun punct. Aceste segmente se comportă ca nişte obstacole.

Fie M baloane cu aer cald care merg în sus ( x-ul rămâne la fel, y creşte). Dacă un balon ajunge la un obstacol, balonul va merge de-a lungul obstacolului, în direcţia în care y creşte. Când balonul a ajuns la capătul obstacolului, el va continua ca înainte să meargă în sus ( x-ul va rămâne neschimbat până la următorul obstacol pe care îl întălneşte).

Pentru fiecare dintre cele M baloane se cere să se afişeze x-ul pe care o să îl aibă după trece de toate obstacolele pe care le va întâlni.

Atenţie! Dacă un balon, mergând în sus, ajunge la capătul unui obstacol, atunci balonul va urma obstacolul. (vezi balonul 1 0 din exemplu)
Atenţie! Baloanele pot începe şi de pe obstacole. În acest caz, ele vor merge pe obstacol. (vezi balonul 13 7 din exemplu)

Date de intrare

Fişierul de intrare obstacole.in se va găsi pe prima linie N şi M. Pe următoarele N linii se vor găsi câte 4 numere x1, y1, x2, y2 reprezentând coordonatele punctelor unui segment. Pe următoarele M linii se vor găsi cate 2 numere x, y reprezentând coordonatele de plecare ale balonului.

Date de ieşire

În fişierul de ieşire obstacole.out se vor găsi M numere, câte unul pe linie, fiecare semnificând x-ul la care o să ajungă balonul corespondent.

Restricţii

• 1 ≤ N, M ≤ 10⁵
• 0 ≤ x, y, x1, y1, x2, y2 ≤ 10⁹ + 10⁴
• Pentru 20% din punctaj, N ≤ 100 şi M ≤ 100.
• Pentru 50% din punctaj, N ≤ 1000 şi M ≤ 1000.

Exemplu

Explicaţie

Cum se trimit solutii?