Wyspa

Limit pamięci: 128 MB

Centrum Gdyni znajduje się na wyspie pośrodku pięknej rzeki. Każdego ranka tysiące samochodów przejeżdżają przez wyspę z zachodu na wschód, z dzielnic mieszkalnych na jednym brzegu rzeki do obszarów przemysłowych po drugiej stronie. Mieszkańcy wjeżdżają na wyspę mostami na zachodnim krańcu i opuszczają ją mostami na wschodnim krańcu.

Wyspa ma kształt prostokąta o bokach równoległych do osi układu współrzędnych. Będziemy więc ją opisywać jako prostokąt we współrzędnych kartezjańskich, którego przeciwległe narożniki mają współrzędne oraz .

Na wyspie jest skrzyżowań, ponumerowanych od do . Skrzyżowanie numer ma współrzędne . Skrzyżowania o współrzędnych postaci są wjazdami na zachodni kraniec wyspy, zaś te o współrzędnych postaci są wyjazdami po wschodniej stronie. Każda ulica jest odcinkiem łączącym dwa skrzyżowania. Niektóre spośród ulic są jedno-, inne zaś dwukierunkowe. Ulice, poza skrzyżowaniami, nie mają punktów wspólnych, nie ma też na wyspie tuneli ani wiaduktów. Nie zakładaj nic ponadto o sieci drogowej (w szczególności, drogi mogą biec brzegiem wyspy, mogą też istnieć skrzyżowania bez wchodzących czy wychodzących z nich ulic).

Z powodu rosnącego natężenia ruchu, prezydent Gdyni zatrudnił Cię w celu sprawdzenia, czy sieć dróg na wyspie jest wystarczająca. Na początek musisz sprawdzić, do ilu skrzyżowań na wschodnim brzegu wyspy można dojechać z każdego ze skrzyżowań na zachodnim brzegu.

Wejście

Pierwszy wiersz standardowego wejścia zawiera cztery liczby całkowite , , oraz (, , ). Są to odpowiednio liczba skrzyżowań w centrum Gdyni, liczba ulic oraz wymiary wyspy.

W każdym z kolejnych wierszy znajdują się dwie liczby całkowite , (, ) - współrzędne -tego skrzyżowania. Żadne dwa skrzyżowania nie mają tych samych współrzędnych.

Kolejne wierszy opisuje ulice. Każdy z tych wierszy zawiera trzy liczby , , (, , ). Opis ten oznacza, że skrzyżowania i są połączone ulicą. Jeśli , jest to jednokierunkowa ulica z do . W przeciwnym wypadku jest to ulica dwukierunkowa. Każda (nieuporządkowana) para pojawi się na wejściu co najwyżej raz.

Możesz założyć, że co najmniej jedno skrzyżowanie na wschodnim brzegu wyspy jest osiągalne z jakiegoś skrzyżowania na zachodnim brzegu.

W testach wartych przynajmniej 30 punktów zachodzi dodatkowy warunek .

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz dla każdego skrzyżowania z zachodniego krańca wyspy. Wiersz ten powinien zawierać liczbę osiągalnych z niego skrzyżowań po wschodniej stronie. Odpowiedzi uporządkuj w kolejności malejącej współrzędnej .

Przykład

Dla danych wejściowych:

5 3 1 3
0 0
0 1
0 2
1 0
1 1
1 4 1
1 5 2
3 5 2

poprawną odpowiedzią jest:

2
0
2

podczas gdy dla danych wejściowych:

12 13 7 9
0 1
0 3
2 2
5 2
7 1
7 4
7 6
7 7
3 5
0 5
0 9
3 9
1 3 2
3 2 1
3 4 1
4 5 1
5 6 1
9 3 1
9 4 1
9 7 1
9 12 2
10 9 1
11 12 1
12 8 1
12 10 1

poprawną odpowiedzią jest:

4
4
0
2

Autor zadania: Jakub Łącki.