题目描述

蛤蟆小时候无聊时喜欢数树，有一天它发现可以数星星，于是成为了一个喜欢研究星际 旅行的天文学家。 在它的想象世界里， 星空可以抽象成一个 $n$ 个点 $m$ 条边的有向图， 点的编号从 $1\sim n$， 边有边权， 并且不存在自环。 蛤蟆发现了一个神奇的性质， 就是这些有向边都是从编号小的点指向编号大的点。

蛤蟆想象自己正在 $1$ 号节点， 正要前往 $x$ 号节点。 蛤蟆还有一个喜欢的数 $r$， 他希望自己到 $x$ 节点走过的路径长度恰好是 $r$。 总所周知， 天文学家允许有一定的误差。 蛤蟆有一个误差参数 $p$。 假设实际走的路径长度是 $t$， 那么只要满足 $r\leq t\leq \dfrac{pr}{p-1}$， 蛤蟆就会满意。

现在蛤蟆想问你， 是否存在这样一条满足要求的路径？ 由于蛤蟆希望前往很多个点， 所以会有多组询问。 由于蛤蟆想象力丰富， 所以会有多组数据。

输入格式

第一行一个整数 $T$ 表示数据组数。

每组数据第一行四个整数 $n,m,q,p$， 含义如上所述。

接下来 $m$ 行每行三个整数 $u,v,w$， 表示一条边。

接下来 $q$ 行每行两个整数 $x,r$， 表示一组询问。

输出格式

对于每组数据， 输出一个长度为 $q$ 的 $01$ 字符串便是答案。 若第 $i$ 组询问有解， 那么字符串的第 $i$ 为就是 $1$， 否则就是 $0$。

【样例 1】

【样例 1 输入】

1
3 3 5 20
1 2 20
2 3 1
1 3 10
2 19
2 20
3 20
3 21
3 9

【样例 1 输出】

11110

数据范围

对于 $100\%$ 的数据， 满足 $1\leq T\leq 1000,1\leq n,m,q,\sum n,\sum m,\sum q\leq 5\times 10^5,2\leq p\leq 20,1\leq w\leq 10^{11},1\leq r\leq 10^{17}$。

大样例