Problem Description

There are $n$ points on the Cartesian plane. The coordinates of the $i$-th point are $(x_i,y_i)$. All points lie inside a rectangle with opposite vertices $(0,0)$ and $(A,B)$.

If $x_i=0$, we say this point is on the west side. If $x_i=A$, we say this point is on the east side.

There are $m$ edges among these points. Each edge may be directed or undirected. It is guaranteed that edges do not intersect anywhere except at the given $n$ points.

Now, for each point on the west side, compute how many points on the east side can be reached by following the edges.

Input Format

The first line contains four integers $n,m,A,B$, separated by spaces.

The next $n$ lines each contain two integers $x_i,y_i$, separated by spaces.

The next $m$ lines each contain three integers $c_i,d_i,k_i$, separated by spaces, describing an edge between $c_i$ and $d_i$. If $k_i=1$, the edge is directed from $c_i$ to $d_i$; otherwise, the edge is undirected.

Output Format

Output several lines, each containing one integer, representing the answer. Output the answers for all west-side points in decreasing order of $y$.

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

2
0
2

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

4
4
0
2

Hint

Explanation for Sample $2$

Constraints

For $100\%$ of the testdata: $1\le n\le 300\ 000;0\le m\le 900\ 000;1\le A,B\le 10^9;0\le x_i\le A;0\le y_i\le B;1\le c_i,d_i\le n;k_i\in \{1,2\}$. It is guaranteed that there is at least one west-side point, and that each unordered pair $\{c_i,d_i\}$ appears at most once.

Translated by ChatGPT 5