Rectangle and Paths
Stepan is about to meet Marysia, but he's stuck on this problem:
You have a rectangle with dimensions a by b, defined by opposite corners at coordinates (0, 0) and (a, b). Inside this rectangle, there are n distinct points, numbered from 1 to n. Each point i has coordinates (x[i], y[i]). Points located at (0, y) are referred to as left points, while those at (a, y) are called right points. Some of these points are connected by segments, which can be traversed either in one direction or both, depending on the segment type. Segments only intersect at their endpoints.
Your task is to determine, for each left point q, how many right points can be reached from it via these segments.
Input
The first line contains four integers: n, m, a, and b – representing the number of points, the number of segments, and the rectangle's dimensions, respectively (1 ≤ n ≤ 300,000, 0 ≤ m ≤ 900,000, 1 ≤ a, b ≤ 10^9).
The next n lines provide the integer coordinates of each point within the rectangle. No two points share the same coordinates. The following m lines describe the segments, each with three integers: x, y, and k (1 ≤ k ≤ 2). If k = 1, the segment is one-way from point x to point y. If k = 2, the segment is bidirectional.
Output
For each left point, output the number of right points that can be reached. The results should be sorted in descending order based on the y-coordinates of the left points.