Problem description


Zagroda
(zagroda)
Limit pamięci: 128 MB
Limit czasu: 8.00 s

Zachary, Michał i Antoni w ramach pracy wakacyjnej zajmują się pilnowaniem owiec pasących się na polanie. Pasterze nie mogą dopuścić, żeby jakakolwiek owca opuściła teren polany. Żeby ułatwić sobie trochę pracę, postanowili postawić płot i zbudować zagrodę, do której zagoniliby wszystkie owce.

Teren polany można reprezentować jako wielokąt wypukły na płaszczyźnie. Chłopaki, skoro jest ich trzech, chcieliby wybrać trzy punkty tego wielokąta i poprowadzić między nimi ogrodzenie. Po zbudowaniu zagrody część owiec będzie się już w niej znajdować (w szczególności te, które stoją w miejscu, przez które będzie przechodził płot), jednakże należałoby zagonić do niej wszystkie pozostałe zwierzęta.

Owce tego lata są wyjątkowo leniwe i uparte, więc zaganianie ich kosztuje Zacharego, Michała i Antoniego wiele wysiłku. Chcieliby zbudować zagrodę tak, żeby później musieć zagonić do niej jak najmniejszą liczbę owiec. Poprosili Cię o pomoc w wyznaczeniu jak powinna wyglądać zagroda.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalna N, M oznaczające kolejno liczbę wierzchołków wielokąta wypukłego opisującego kształt polany oraz liczbę owiec. W następnych N wierszach następuje opis polany. Każdy wiersz składa się z dwóch liczb całkowitych x, y oznaczających, że w punkcie x, y znajduje się wierzchołek wielokąta. Wierzchołki podane są w kolejności wg wskazówek zegara. W następnych M wierszach znajdują się współrzędne kolejnych owiec. Każdy wiersz składa się z dwóch liczb całkowitych x, y określających, że w punkcie x, y stoi owca.

Wyjście

W pierwszym wierszu wyjścia powinny znaleźć się trzy liczby naturalne Z, M, A oznaczające numery wierzchołków wielokąta określającego kształt polany, które powinny być wierzchołkami trójkątnej zagrody zbudowanej przez chłopaków. Wśród wszystkich możliwych odpowiedzi należy podać najmniejszą leksykograficznie.

Ograniczenia

1 ≤ N, M ≤ 2000,  − 109 ≤ x, y ≤ 109. Możesz założyć, że współrzędne owiec znajdują się wewnątrz wielokąta (w szczególności mogą znajdować się na jego bokach lub wierzchołkach).

Przykład

Wejście Wyjście Wyjaśnienie
5 5
-3 3
0 4
4 1
2 -1
-1 -3
-1 2
0 3
-1 -1
1 2
-1 -2
1 2 5