Problem Description

In a Cartesian coordinate system, there are $n$ points, where the coordinates of the $i$-th point are $(x_i, y_i)$. All points are within a rectangle defined by $(0,0)$ and $(A,B)$ as opposite vertices.

If $x_i = 0$, the point is considered to be on the west side. If $x_i = A$, the point is considered to be on the east side.

There are $m$ edges between these points, each of which can be either directed or undirected, and are guaranteed not to intersect anywhere except at their endpoints.

Your task is to determine, for each point on the west side, how many points on the east side can be reached by following the edges.

Input Format

The first line contains four space-separated numbers $n, m, A, B$.

The next $n$ lines each contain two space-separated numbers $x_i, y_i$.

The next $m$ lines each contain three space-separated numbers $c_i, d_i, k_i$, indicating 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 a number representing the answer. Output the answers for all points on the west side in descending order of their $y$ coordinates.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2
0
2

Input Sample #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

Output Sample #2

4
4
0
2

Notes

Sample 2 Explanation

Data Range

For $100\%$ of the data, $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 point on the west side, and each unordered pair $\{c_i, d_i\}$ appears only once.

见题面 Input 部分

见题面 Output 部分