连接弗拉特兰（Flatland）首都与其邻近城市的铁路系统已经非常陈旧。为了对其进行现代化改造，决定从首都到其中一个车站开通一条特快列车线路。

弗拉特兰的铁路网共有 $n$ 个车站，编号为 $1$ 到 $n$，首都的编号为 $1$。车站之间共有 $m$ 条单向铁路线段。对于每一条线段，特快列车都可以从编号较小的车站行驶到编号较大的车站。已知每条线段的行驶时间。

我们将“路径”定义为一系列线段的序列，使得第一条线段从首都出发，且对于任意两条连续的线段，第二条线段的起点与第一条线段的终点相同。路径的行驶时间等于所有这些线段行驶时间的总和，车站的停留时间忽略不计。

弗拉特兰交通部计划考虑几种特快列车路径方案。每个方案由目标车站编号和预估行驶时间来表征。然而，交通部明白，完全满足预估行驶时间的要求可能是不可能的。因此，他们使用参数 $p$ 来评估路径的可行性：如果路径的行驶时间为 $x$，且预估行驶时间为 $r$，则当 $r \leqslant x \leqslant \frac{p}{p-1} \cdot r$ 时，该路径对于预估时间 $r$ 是可行的。

你需要编写一个程序，根据弗拉特兰铁路网的描述和路径方案，确定对于每个方案，是否存在满足该方案的可行路径。

输入格式

本题中，单次程序运行需处理多个测试用例。

输入的第一行包含一个整数 $t$ —— 测试用例的数量 ($1 \leqslant t \leqslant 1000$)。

接下来依次描述各个测试用例，格式如下：

第一行包含四个整数 $n, m, q, p$ —— 车站数量、线段数量、需要考虑的方案数量，以及定义允许超出预估行驶时间范围的参数 ($2 \leqslant n \leqslant 500\,000, 1 \leqslant m \leqslant 500\,000, 1 \leqslant q \leqslant 500\,000, 2 \leqslant p \leqslant 20$)。

接下来的 $m$ 行，每行包含三个整数，描述第 $i$ 条线段：$v_i, u_i, d_i$ —— 起始车站、到达车站以及特快列车通过该线段的时间 ($1 \leqslant v_i < u_i \leqslant n, 1 \leqslant d_i \leqslant 10^{11}$)。保证对于任何车站，都至少存在一条从首都出发并到达该车站的路径。

接下来的 $q$ 行，每行包含两个整数 $f_i$ 和 $r_i$ —— 要求检查是否存在到达车站 $f_i$ 且预估行驶时间为 $r_i$ 的可行路径 ($2 \leqslant f_i \leqslant n, 1 \leqslant r_i \leqslant 10^{17}$)。

保证所有测试用例中 $n$ 的总和、$m$ 的总和以及 $q$ 的总和均不超过 $500\,000$。

输出格式

输出 $t$ 行，每行对应一个输入测试用例的结果。

对于每个测试用例，输出一个长度为 $q$ 的字符串，由字符 0 和 1 组成。如果第 $i$ 的方案存在可行路径（即到达车站 $f_i$ 的路径，其行驶时间在区间 $[r_i, \frac{p}{p-1} \cdot r_i]$ 内），则第 $i$ 个字符 $s_i$ 应为 1，否则为 0。

样例

输入格式 1

2
3 3 5 20
1 2 20
2 3 1
1 3 10
2 19
2 20
3 20
3 21
3 9
7 10 5 5
1 2 15
1 3 10
2 4 21
3 4 30
2 5 14
3 5 31
4 6 3
5 6 14
1 7 39
5 7 13
7 42
7 43
7 44
5 39
6 44

输出格式 1

11110
10111

输入格式 2

1
4 6 5 2
1 2 1
2 3 1
3 4 1
1 2 70
2 3 120
3 4 4
4 90
4 2
4 10
4 37
2 34

输出格式 2

11010

说明

在第二个样例中： 第一个查询中，时间为 $1 + 120 + 1 = 122$ 的路径符合要求。 第二个查询中，时间为 $1 + 1 + 1 = 3$ 的路径符合要求。 * 第四个查询中，时间为 $70 + 1 + 1 = 72$ 的路径符合要求。 对于第三个和第五个查询，不存在任何符合要求的路径。