题目描述

徐老师最近在复习《最短路》相关的算法

在一道题目中，有 $n$ 个节点和 $m$ 条双向边，节点编号分别为 $1 \sim n$，第 $i$ 条边连接 $u_i,v_i$ 这两个点，并且边的权值为 $w_i$

对于一条 $x$ 到 $y$ 的路径，路径长度即为路上所有边的权值之和

题目会给出起点 $st$ 和终点 $ed$，问起点到终点的最小路径长度是多少。

但是这个题目太简单了，也太没意思了，于是徐老师决定修改一下题目:

也就是例如一条路径上经过了三条边，边权分别为 $w_1,w_2,w_3$，那么这条路径长度即为 $w_1 \& w_2 \& w_3$

给定一个图，包含 $n$ 个节点和 $m$ 条双向边，节点编号分别为 $1 \sim n$，第 $i$ 条边连接 $u_i,v_i$ 这两个点，并且边的权值为 $w_i$

对于一条 $x$ 到 $y$ 的路径，路径长度即为路上所有边的权值与(&)之和

并且有 $T$ 次询问，每次询问给出一个起点 $st_i$ 和一个终点 $ed_i$

询问 $st_i$ 到 $ed_i$ 的所有路径中是否包含路径长度 $>= V$ 的路径（在所有询问中 $V$ 是相同的）

输入格式

第一行输入四个整数 $n,m,V$，含义如题所述

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条连接节点 $u_i$ 和 $v_i$ 的无向边，边权为 $w_i$（可能存在重边）

然后输入一行包含一个整数 $T$ 表示询问次数

接下来 $T$ 行，每行包含两个整数 $st_i,ed_i$ 表示一次询问

输出格式

对于每次询问，如果存在符合条件的路径，则输出 Yes，否则输出 No

数据范围

对于 $10\%$ 的数据，$n \le 10$。

另外有 $10\%$ 的数据，满足这张图为一棵树，且无重边。

另外有 $20\%$ 的数据，$V$ 为 $2$ 的若干次幂。

对于 $100\%$ 的数据，保证 $1\le n \le 10^5$，$0\le m \le 5\times 10^5$，$1\le T\le 5\times 10^5 ，0\le V,w_i< 2^{60}$。

样例输入1

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

样例输出1

Yes

样例输入2

4 3 0
1 2 1 
2 3 2
3 4 3
1
1 3

样例输出2

Yes

样例输入3

9 8 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
4
1 6
2 7
7 6
1 8

样例输出3

Yes
No
Yes
No

样例解释3

对于第一次询问，可以选择 $1->3->4->5->6$ 这条路线，路径长度为 $7 \& 14 \& 7 \& 6 = 6$