Traffic

The center of Gdynia lies on an island in the middle of the Kacza river. Every morning thousands of cars cross the island from the residential districts on the western bank (entering through junctions on the western side of the island) to the industrial areas on the eastern bank (leaving through junctions on the eastern side).

The island is a rectangle whose sides are parallel to the axes. We model it as an $A \times B$ rectangle in the Cartesian plane whose opposite corners are $(0, 0)$ and $(A, B)$.

There are $n$ junctions on the island, numbered from $1$ to $n$. Junction $i$ has coordinates $(x_i, y_i)$. A junction with coordinates $(0, y)$ lies on the western side of the island; a junction with coordinates $(A, y)$ lies on the eastern side. Junctions are connected by streets, each a straight segment joining two junctions. A street is either one-way or two-way. No two streets share any point other than a common endpoint at a junction (there are no bridges or tunnels). Nothing else about the network is assumed: streets may run along a bank, and a junction may have no incoming or outgoing streets.

For every junction on the western side, determine how many junctions on the eastern side are reachable from it.

The first line contains four integers $n$, $m$, $A$, $B$ ($1 \le n \le 300\,000$, $0 \le m \le 900\,000$, $1 \le A, B \le 10^9$): the number of junctions, the number of streets, and the dimensions of the island.

Each of the next $n$ lines contains two integers $x_i$, $y_i$ ($0 \le x_i \le A$, $0 \le y_i \le B$), the coordinates of junction $i$. No two junctions share the same coordinates.

Each of the next $m$ lines contains three integers $c_i$, $d_i$, $k_i$ ($1 \le c_i, d_i \le n$, $c_i \ne d_i$, $k_i \in \{1, 2\}$) describing a street between junctions $c_i$ and $d_i$. If $k_i = 1$ the street is one-way from $c_i$ to $d_i$; if $k_i = 2$ it can be driven in both directions. Each unordered pair $\{c_i, d_i\}$ appears at most once.

At least one junction on the western side can reach some junction on the eastern side.

Print one line for each junction on the western side. Each line contains the number of junctions on the eastern side reachable from that junction. Output the western junctions in order of decreasing $y$-coordinate.