题目背景

翻译自 ROI 2019 D1T3。

Flatland 的首都需要与邻近的城市之间建立铁路联系，而现有的铁路系统已经过时。为了优化铁路系统，需要开通一列从首都到另一个城市的高速电车。Flatland 铁路网络总共有 $n$ 个站点，从 $1$ 到 $n$ 进行编号，首都的编号是 $1$。在各个站点之间存在 $m$ 条单向线路，每条线路的行驶时间已知。

题目描述

计划部门打算考虑几个不同的高速电车路线方案。每个方案由一个目标站点和预计行驶时间来定义。然而，部门知道实际的行驶时间可能无法完全符合预期。因此，他们使用参数 $p$ 来评估路线的可行性：对于给定的预计时间 $r$，如果 $r\le x\le\frac{p}{p-1}\times r$，其中 $x$ 是行驶时间的总和，则认为路线是可行的。

编写一个程序，根据 Flatland 铁路网络的描述和各个路线方案，确定每个方案是否存在可行的高速电车路线。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数。

接下来的若干行描述每组测试数据。

每组测试数据的第一行包含四个整数 $n,m,q,p$，分别表示站点数量、线路数量、要考虑的路线方案数量和允许的时间偏差参数。

接下来的 $m$ 行描述每条线路，每行包含三个整数 $v_i,u_i,d_i$，分别表示起始站点、终点站点和行驶时间。

接下来的 $q$ 行描述每个路线方案，每行包含两个整数 $f_i$ 和 $r_i$，分别表示目标站点和预计行驶时间。

输出格式

对于每个测试用例，输出一行长度为 $q$ 的字符串 $s$，其中第 $i$ 个字符 $s_i$ 等于 $1$ 表示存在可行的高速电车路线，行驶时间在区间 $[r_i,\frac{p}{p-1}\times r_i]$ 内；否则，$s_i$ 等于 $0$ 表示不存在可行的高速电车路线。

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

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

11010

提示

样例 $1$ 解释：

样例 $2$ 解释：

第一个查询的路线时间为 $1 + 120 + 1 = 122$，符合预期。

第二个查询的路线时间为 $1 + 1 + 1 = 3$，符合预期。

第四个查询的路线时间为 $70 + 1 + 1 = 72$，符合预期。

对于第三个和第五个查询，没有可行的路线符合预期。

数据范围：

对于 $100\%$ 的数据，$1\le t\le1000,1\le v_i<u_i\le n\le500000,1\le m\le500000,1\le q\le500000,2\le p\le20,1\le d_i\le10^{11},2\le f_i\le n,1\le r_i\le10^{17}$。

各个 Subtask 分值及特殊性质：

Subtask	分值	$n$	$m$	$q$	其它特殊性质
$1$	$15$	$n\le10$	$m\le10$	$q\le10$
$2$	$24$	$\sum n\le5000$	$\sum m\le5000$	$\sum q\le5000$	$r_i\le5000$
$3$	$17$		$m=2n-2$	$q\le10$	$p=2$，且对于每个 $i<n$，恰有两条从 $i$ 出发到 $i+1$ 的线路
$4$	$11$				对于每个 $i<n$，恰有两条从 $i$ 出发到 $i+1$ 的线路
$5$		$\sum n\le1000$	$\sum m\le2000$		所有 $r_i$ 值相等
$6$
$7$