Gdynia 市中心位于 Kacza 河中央的一个岛上。每天早晨，成千上万辆汽车从河西岸的住宅区（通过桥梁连接到岛西侧的交叉路口）穿过该岛，前往东岸的工业区（通过从岛东侧的交叉路口出发的桥梁）。

该岛呈矩形，其边界与基准方向平行。因此，我们将其视为笛卡尔坐标系中的一个 $A \times B$ 矩形，其对角顶点位于 $(0, 0)$ 和 $(A, B)$。

岛上有 $n$ 个交叉路口，编号为 $1$ 到 $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$)。它们分别表示 Gdynia 市中心的交叉路口数量、街道数量以及岛屿的尺寸。

接下来的 $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 \neq d_i$，$k_i \in \{1, 2\}$) 表示。其含义是交叉路口 $c_i$ 和 $d_i$ 由一条街道连接。如果 $k_i = 1$，则这是一条从 $c_i$ 到 $d_i$ 的单向街道。否则，该街道可以双向通行。每个无序对 $\{c_i, d_i\}$ 在输入中最多出现一次。

你可以假设在岛的西侧至少存在一个交叉路口，从该路口可以到达岛东侧的某个交叉路口。

输出格式

你的程序应该向标准输出写入一行，对应岛西侧的每个交叉路口。

该行应包含从该交叉路口可达的岛东侧交叉路口数量。

输出应按照交叉路口的 $y$ 坐标降序排列。

数据范围

此外，在价值至少 30 分的测试用例中，$n, m \le 6\,000$。

样例

输入样例 1

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

输出样例 1

2
0
2

输入样例 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

输出样例 2

4
4
0
2