WiFi

Sieć Wi-Fi

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów

Hektor wpadł na pomysł, który uczyni go bogatym. Postanowił napisać program rozwiązujący popularny problem prawidłowego ustawienia routera WiFi tak, aby każdy z komputerów w mieszkaniu miał do niego dostęp ( tj najkrótsza droga łącząca router z komputerem nie przechodziła przez żadną ze ścian). 

Pierwsza wersja programu będzie mocno uproszczona - będzie obsługiwać mieszkania z co najwyżej trzema komputerami i routery o nieskończonym zasięgu.

Czy Ty potrafisz napisać taki program?

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy:

Pierwsza linia zawiera 3 liczby całkowite R, N, M ( 2 <= R <= 10000, 2 <= N <= 3, 1 <= M <= 100 ). Obszar poszukiwań ustawienia routera należy ograniczyć do takich (X,Y) że -R < ( X, Y ) < R. N oznacza ilość komputerów w sieci, M to ilość ścian w rozpatrywanym obszarze.

Następne N lini zawiera po 2 liczby całkowite X,Y  ( -R < (X, Y) < R ) oznaczające położenie komputerów.

Następne M lini zawiera po 4 liczby całkowite x₀, y₀, x₁, y₁ ( -R < (x₀, y₀, x₁, y₁ ) < R ) określające odcinek reprezentujący pojedynczą ściane.

Możesz założyć, że żadne ściany się nie przecinają (aczkolwiek mogą mieć wspólne końce). Żaden komputer nie znajduje się wewnątrz ściany.

Wyjście

Dla każdego przypadku testowego określ, czy da sie ustawić router tak aby sygnał z routera dochodził do każdego komputera bez przechodzenia przez ściany.

Przykład