교통

그디니아(Gdynia)의 중심부는 카차(Kacza)강 한가운데의 섬에 있다. 매일 아침 수천 대의 자동차가 강 서쪽의 주거 지역에서(섬 서쪽에 있는 교차로를 통해) 섬을 가로질러 강 동쪽의 산업 지역으로(섬 동쪽에 있는 교차로를 통해) 이동한다.

섬은 각 변이 좌표축과 평행한 직사각형이며, 마주 보는 두 꼭짓점이 $(0, 0)$과 $(A, B)$인 $A \times B$ 직사각형으로 나타낸다.

섬에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 교차로가 있다. $i$번 교차로의 좌표는 $(x_i, y_i)$이다. 좌표가 $(0, y)$인 교차로는 섬의 서쪽에 있고, 좌표가 $(A, y)$인 교차로는 섬의 동쪽에 있다. 교차로들은 거리로 연결되며, 각 거리는 두 교차로를 잇는 선분이다. 각 거리는 일방통행이거나 양방향이다. 어떤 두 거리도 교차로에서의 공통 끝점을 제외하고는 어떤 점도 공유하지 않는다(다리나 터널은 없다). 그 밖에는 도로망에 대해 아무것도 가정하지 않는다. 강변을 따라 나 있는 거리가 있을 수 있고, 드나드는 거리가 하나도 없는 교차로가 있을 수도 있다.

서쪽에 있는 각 교차로에 대해, 그 교차로에서 도달할 수 있는 동쪽 교차로가 몇 개인지 구하라.

첫째 줄에 네 정수 $n$, $m$, $A$, $B$가 주어진다($1 \le n \le 300\,000$, $0 \le m \le 900\,000$, $1 \le A, B \le 10^9$). 각각 교차로의 수, 거리의 수, 섬의 크기를 나타낸다.

다음 $n$개의 줄에는 각각 두 정수 $x_i$, $y_i$가 주어진다($0 \le x_i \le A$, $0 \le y_i \le B$). $i$번 교차로의 좌표이다. 좌표가 같은 교차로는 없다.

다음 $m$개의 줄에는 각각 세 정수 $c_i$, $d_i$, $k_i$가 주어진다($1 \le c_i, d_i \le n$, $c_i \ne d_i$, $k_i \in \{1, 2\}$). 교차로 $c_i$와 $d_i$를 잇는 거리를 나타낸다. $k_i = 1$이면 $c_i$에서 $d_i$로 가는 일방통행이고, $k_i = 2$이면 양방향으로 다닐 수 있다. 순서 없는 쌍 $\{c_i, d_i\}$는 입력에 많아야 한 번 나타난다.

서쪽 교차로 중 적어도 하나는 동쪽의 어떤 교차로에 도달할 수 있다.

서쪽에 있는 각 교차로마다 한 줄씩 출력한다. 각 줄에는 그 교차로에서 도달할 수 있는 동쪽 교차로의 수를 출력한다. 서쪽 교차로는 $y$좌표가 큰 것부터 작은 순서로 출력한다.