配点 : 300 点
問題文
整数 N,M,K 和 按字典顺序比较 N 頂点 M 给出了边的无向图。在图表的顶部 1 减去 N 号码位于侧面。 它的编号为 1 减去 M 。侧面 i (1 ≤ i ≤ M) 是顶点 A_i 和 边缘 B_i 和边缘上的非负整数。 C_i 位于此处。 给出
Q 查询。 在查询i 番目 (1 ≤ i ≤ Q) 查询整数 D_{i} 已给出,因此我们需要一组满足以下所有条件的整数。 查找 (u,v) 的编号。 它是
- 1\le u\lt v\le N
- (C_{j} \oplus D_{i})\lt K 的边 仅通过 j 顶点 可以移动到 u 到顶点 v 可能会上升到
但是 \oplus 以位为单位 \text{XOR} 代表一个操作。
位单位 \text{XOR} 什么是操作? 按位
非負整数 X,Y 按位 \text{XOR} 演算、 X\oplus Y 定义如下。- X\oplus Y 以二进制表示法 2^{k}地点(0\le k) 是 第 A,B 以二进制表示法 2^{k} 如果数字不同 1 ,否则 输出 0 。
制約
- 所有输入均为整数
- 2\le N\le 10^{5}
- 1\le M\le 10^{5}
- 0\le K\lt 2^{30}
- 1\le A_{i} \lt B_{i}\le N (1 ≤ i ≤ M)
- 0\le C_{i}\lt 2^{30} (1 ≤ i ≤ M)
- 1\le Q\le 10^{5}
- 0\le D_{i}\lt 2^{30} (1 ≤ i ≤ Q)
入力
输入是按以下格式从标准输入给出的。
N M K
A_{1} B_{1} C_{1}
A_{2} B_{2} C_{2}
\vdots
A_{M} B_{M} C_{M}
Q
D_{1}
D_{2}
\vdots
D_{Q}
出力
Q 行。 i 行目 (1\le i\le Q) 是 写入 i 个查询的答案。
入力例 1
4 5 5 1 2 17 1 3 4 2 3 20 2 4 3 3 4 5 4 0 7 16 167
出力例 1
2 6 3 0
- 1 个查询中,边 您只能通过 2,4 。 在第
- 2 个查询中,边 您只能通过 2,4,5 。 在第
- 3 个查询中,边 您只能通过 1,3 。 在第
- 4 个查询中,没有可遍历的边。
入力例 2
9 13 488888932 2 7 771479959 3 8 783850182 5 7 430673756 6 8 350738034 4 9 400768807 2 3 83653266 1 2 829786563 5 8 357613791 7 9 579696618 3 7 423191200 3 5 867380255 1 9 907715012 6 9 1033650694 8 498260055 144262908 117665696 848664012 983408133 32610599 478007408 134182829
出力例 2
16 7 5 13 13 16 16 5