P11082 [ROI 2019] 高速电车 (Day 1)

翻译自 [ROI 2019 D1T3](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf)。 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$ 表示不存在可行的高速电车路线。

### 样例 $1$ 解释：  ### 样例 $2$ 解释：  第一个查询的路线时间为 $1 + 120 + 1 = 122$，符合预期。 第二个查询的路线时间为 $1 + 1 + 1 = 3$，符合预期。 第四个查询的路线时间为 $70 + 1 + 1 = 72$，符合预期。 对于第三个和第五个查询，没有可行的路线符合预期。 ### 数据范围： 对于 $100\%$ 的数据，$1\le t\le1000,1\le v_i