Zadanie eliminacyjne w konkursie WIPING5 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Laser

Na płaszczyźnie rozmieszczono ponumerowane kolejno bardzo cienkie, dwustronne zwierciadła. W pewnym miejscu wyemitowano z lasera wiązkę światła – Twoje zadanie polega na sprawdzeniu, od których zwierciadeł odbije się promień.

Wejście

W pierwszym wierszu znajdują się 4 liczby zmiennoprzecinkowe lx, ly, dx, dy określające kolejno współrzędne punktu, z którego wyszła wiązka lasera, oraz kierunek, w którym podąża. W kolejnym wierszu znajduje się liczba zwierciadeł n. W kolejnych n wierszach znajdują się 4 liczby zmiennoprzecinkowe x1, y1, x2, y2 określające odpowiednio współrzędne początku i końca zwierciadła. Numerowanie zwierciadeł zaczyna się od 1.

Wyjście

Numery zwierciadeł, od których kolejno odbiła się wiązka. Testy są tak dobrane, że promień zawsze odbije się od skończonej liczby luster.

Przykład

Wejście:

1 1 1 0
3
4.5 0.5 5.5 1.5
4 4 6 5
5.5 2.5 4.5 3.5

Wyjście:

1 3

Graficzna ilustracja przykładu: