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 in plan, neorizontale si neverticale care nu se intersecteaza in niciun puct. Aceste segmente se comporta ca niste obstacole.

Fie M baloane cu aer cald care merg in sus ( x-ul ramane la fel, y creste). Daca un balon ajunge la un obstacol, balonul va merge de-a lungul obstacolului, in directia in care y creste. Cand balonul a ajuns la capatul obstacolului, el va continua ca inainte sa mearga in sus ( x-ul va ramane neschimbat pana la urmatorul obstacol pe care il intalneste).

Pentru fiecare dintre cele M baloane se cere sa se afiseze x-ul pe care o sa il aiba dupa trece de toate obstacolele pe care le va intalni.

Atentie! Daca un balon, mergand in sus, ajunge la capatul unui obstacol, atunci balonul va urma obstacolul. (vezi balonul 1 0 din exemplu)
Atentie! Baloanele pot incepe si de pe obstacole. In acest caz, ele vor merge pe obstacol. (vezi balonul 13 7 din exemplu)

Date de intrare

Fişierul de intrare obstacole.in se v-a gasi pe prima linie N si M. Pe urmatoarele N linii se vor gasi cate 4 numere x1, y1, x2, y2 reprezentand coordonatele punctelor unui segment. Pe urmatoarele M linii se vor gasi cate 2 numere x, y reprezentand coordonatele de plecare a balonului.

Date de ieşire

În fişierul de ieşire obstacole.out se vor gasi M numere, cate unul pe linie, fiecare semnificand x-ul la care o sa ajunga balonul corespondent.

Restricţii

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

Exemplu

Explicaţie

Cum se trimit solutii?