题目描述

译自 ROI 2019 Day1 T3. Экспресс 20/19

给一个有 $n$ 个结点 $m$ 条边的 DAG。所有边均从编号小的结点指向编号大的结点。给出每条边的长度。

给一个常数 $p$。我们估计某条路径的总长度（这条路径上每条边的长度之和）为 $r$，而它的总长度实际上为 $x$，如果

则称「估计这条（实长为 $x$ 的）路线的长度为 $r$ 是合理的」。

有 $q$ 组查询。第 $i$ 组查询包含两个数 $f_i, r_i$。对于每组查询，试求是否存在一条以 $1$ 号结点为起点，以 $f_i$ 为终点的路径，满足：估计这条路线的长度为 $r_i$ 是合理的。

输入格式

每个输入文件包含多组数据。 文件的第一行：数据组数 $t$。

每组数据的第一行：$n, m, q, p$。 接下来 $m$ 行：$v_i, w_i, d_i$，表示一条边。 接下来 $q$ 行：$f_i, r_i$，表示一个查询。

输出格式

对于每组数据输出一行，每行一个长度为 $q$ 的 01 字符串 $s$。若 $s_i=1$，则在本组数据中第 $i$ 个查询是有解的；若 $s_i=0$，则在本组数据中第 $i$ 个查询是无解的。

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

输出

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

输出

11010

数据范围与提示

$1 \leqslant t \leqslant 1000$, $2 \leqslant n \leqslant 500\ 000$, $1 \leqslant m \leqslant 500\ 000$, $1 \leqslant q \leqslant 500\ 000$, $2 \leqslant p \leqslant 20$, $1 \leqslant d_i \leqslant 10^{11}$, $1 \leqslant r_i \leqslant 10^{17}$。保证 $\sum n,m,q \leqslant 500000$。