题目描述

你还停留在解决传统路径查询问题的年纪吗？

在研读论文《分布式次线性时间精确最短路径算法》后，你已经掌握了如何在 $O(D^{1/3}⋅(n\ logn)^{2/3})$ 时间复杂度内解决分布式单源最短路径问题。为了实践所学知识，小蓝鱼为你准备了以下练习题。

小蓝鱼有一个包含 $n$ 个顶点和 $m$ 条双向边的图。顶点编号为 $1$ 至 $n$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，权值为 $w_i$。

对于图中任意两顶点 $u$ 和 $v$ 之间的路径，我们定义该路径的 "价值" 为路径中所有边权值的按位与运算的结果。

作为高价值路径的爱好者，小蓝鱼设定了一个恒定阈值 $V$。当且仅当路径价值 $≥V$ 时，小蓝鱼才会青睐这条路径。

接下来小蓝鱼会提出 $q$ 次查询，每次查询用整数对 $(u_i,\ v_i)$ 表示。对于每个查询，你需要判断是否存在一条从 $u_i$ 到 $v_i$ 且让小蓝鱼青睐的路径。

输入格式

每个测试文件仅含一组测试数据。

首行包含四个整数 $n,\ m,\ q,\ V$（$1≤n≤10^5$，$0≤m≤5\times 10^5$，$1≤q≤5\times10^5$，$0≤V<2^{60}$），分别表示顶点数、边数、查询数和价值阈值。

随后 $m$ 行，每行三个整数 $u_i,\ v_i,\ w_i$（$1≤u_i,\ v_i≤n$，$u_i≠v_i$，$0≤w_i<2^{60}$），描述连接 $u_i$ 和 $v_i$ 的双向边及其权值。同一对顶点间可能存在多条边。

最后 $q$ 行，每行两个整数 $u_i,\ v_i$（$1≤u_i,\ v_i≤n$，$u_i≠v_i$），表示一次查询。

输出格式

对每个查询输出一行。若存在满足条件的路径则输出 Yes，否则输出 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

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

Yes

样例1解释

我们用 & 符号表示按位与运算。

第一个示例测试用例解析：

• 对于第一个查询，有效路径为 $1→3→4→5→6$，其路径价值计算为 $7\ \&\ 14\ \&\ 7\ \&\ 6=6≥5$（满足阈值 $5$）。
• 对于第三个查询，有效路径为 $7→3→4→5→6$，其价值 $15\ \&\ 14\ \&\ 7\ \&\ 6=6≥5$。
• 对于第四个查询，由于顶点 $1$ 和 $8$ 之间不存在任何路径，故答案为 No。

在第二个示例测试用例的唯一查询中，我们可以考虑由第 $2$ 条边和第 $4$ 条边组成的路径。其路径价值计算为 $5\ \&\ 6=4$，满足阈值 $4$ 的要求。