#P18649. XOR Reachable

XOR Reachable

XOR Reachable

题目描述

给定整数 N,M,KN,M,K 和一张有 NN 个顶点、MM 条边的无向图。顶点编号为 1,…,N1,\ldots,N,边编号为 1,…,M1,\ldots,M。第 ii 条边连接顶点 AiA_i 和 BiB_i,非负整数边权为 CiC_i。

图中可能有重边,不含自环。输入中的 Ai<BiA_i<B_i 仅将每条无向边的两个端点按大小排列。

有 QQ 次询问,第 ii 次询问给出一个整数 DiD_i。请计算满足下列条件的整数对 (u,v)(u,v) 的数量:

  • 1≤u<v≤N1\le u<v\le N。
  • 可以仅使用满足 (Cj⊕Di)<K(C_j\oplus D_i)<K 的边 jj,从顶点 uu 到达顶点 vv。

其中 ⊕\oplus 表示按位异或运算。

输入格式

N M K
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M
Q
D_1
D_2
...
D_Q

输入仅包含一组数据,所有数均为整数。

输出格式

输出 QQ 行。第 ii 行输出一个整数,表示第 ii 次询问的答案。

数据范围

  • 2≤N≤1052\le N\le10^5。
  • 1≤M≤1051\le M\le10^5。
  • 0≤K<2300\le K<2^{30}。
  • 1≤Ai<Bi≤N1\le A_i<B_i\le N。
  • 0≤Ci<2300\le C_i<2^{30}。
  • 1≤Q≤1051\le Q\le10^5。
  • 0≤Di<2300\le D_i<2^{30}。

样例输入 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

样例输入 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