题目描述

有一张 $n$ 个点 $m$ 条边的无向图，节点编号从 $1\sim n$，第 $i$ 条边连接节点 $u_i,v_i$，边权为 $w_i$。

对于一条从 $u$ 到 $v$ 的路径，小Z认为路径的价值为路径上所有边按位与（$\rm{bitwise} \rm{AND}$）的结果。如果一条路径的价值至少为 $V$，则小Z会喜欢这条路径。

因此，小Z会给你 $q$ 次询问，每次询问两个点 $u,v$ 之间是否存在他喜欢的路径。

输入格式

第一行输入四个整数 $n,m,q,V$。

接下来的 $m$ 行，每行输入三个整数 $u_i,v_i,w_i$ 表示一条边。

接下来的 $q$ 行，每行输入两个整数 $u_i,v_i$ 表示一次询问。

输出格式

每个询问输出一行，若 $u,v$ 之间存在小Z喜欢的路径则输出 $\rm{Yes}$，否则输出 $\rm{No}$。

输入输出样例

9 8 4 5
1 2 8
1 3 7
2 4 1
3 4 14
2 5 9
4 5 7
5 6 6
3 7 15
1 6
2 7
7 6
1 8

Yes
No
Yes
No

样例 $\tt \#1$说明

第一组样例中，第一次询问的路径可以是 $\{1,3,4,5,6\}$，价值为 $6$；第三次询问的路径可以是 $\{7,3,4,5,6\}$，价值也是 $6$。

3 4 1 4
1 2 3
1 2 5
2 3 2
2 3 6
1 3

Yes

样例 $\tt \#2$说明

走第二条边和第四条边，价值为 $4$。

数据范围

对于 $30\%$ 的数据，$n,m,q\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5,0\leq m\leq 5\times 10^5,1\leq q\leq 5\times 10^5,0\leq V,w_i<2^{60}$。保证没有自环，询问的两点不相同。