#H1046. Light

Light

题目描述

神遗弃了祂的子民。


远古太阳神自杀成功后,东大陆的白昼被阿蒙偷走,天气因此变化无常。99%99\% 以上的生物死亡或异变。东大陆沦为神弃之地。

由于“大地的恩赐”,白银城众人得以幸存。幸存者一直在探寻如何离开神弃之地。为了安全地探索未知的暗域,戴里克常常向“愚者”先生询问神弃之地某天某地的天气。

神弃之地有 nn 个遗址,其中有 mm 条无向路径连接这些遗址。不会有路径的两端连向同一座遗址,也不会有两条路径连接相同的遗址。在第 jj 天,ii 号遗址的天气为 fi,jf_{i,j}。戴里克已经知道了第 00 天每座遗址的天气 fi,0f_{i,0}。根据经验,他知道之后的每一天每座遗址的天气,都将会变为所有与该遗址直接相连的遗址的前一天的天气在 basebase 进制下做不进位加法值,即

fx,j=fy1,j1fy2,j1fyk,j1f_{x,j}=f_{y1,j-1}\oplus f_{y2,j-1}\oplus \cdot\cdot\cdot\oplus f_{yk,j-1}

其中 j1j\ge 1y1,y2,,yky_1,y_2,\cdots,y_k 是所有与 xx 号遗址直接相连的遗址,\oplusbasebase 进制下的不进位加法。

因为丰收女神陨落后留下了诅咒,进制 basebase 并不是固定的

戴里克会向“愚者”先生提 qq 个问题。每次他会给出三个数:询问点 xx,进制 basebase,还有天数 dayday

为了不让洛薇雅长老察觉,戴里克给出的 dayday 经过加密。解密方法为:设上一次相同进制 basebase 的询问解密后为 last_daylast\_day,本次询问给的数为 dd,则当前 dayday 值为 last_day+2dlast\_day+2^dlast_daylast\_day 初始值为 00

戴里克不会愚弄“愚者”。所以相同进制下,给定的 dd 不会重复。

作为“愚者”的虔诚信徒,你需要代替“愚者”先生回答戴里克, basebase 进制下,dayday 天后,xx 点的天气。

输入格式

第一行三个正整数 nnmmqq,分别代表点数,边数和询问数。
接下来一行 nn 个正整数 fi,0f_{i,0}
接下来 mm 行,每行两个正整数 xxyy,代表 xxyy 之间有一条无向边。
接下来 qq 行,每行三个整数 xxbasebasedd。其中 dd 经过加密,解密方法题目描述里已给出。
所有输入均以十进制形式给出。

输出格式

一共 qq 行,对于每个询问分别输出一个整数表示答案,用十进制输出。

3 3 4
2 0 4
1 2
1 3
2 3
1 2 4
1 7 4
1 5 3
3 3 0
4
4
2
2
5 6 6
2 0 5 0 0
1 3
4 5
1 5
1 2
2 3
1 4
4 3 2
1 2 1
2 5 2
1 2 0
3 2 2
2 7 4
5
5
13
5
2
3

数据规模与约定

2020 个测试点。
对于 30%30\% 的数据,n10n\leq 10q10q\leq 10d5d\leq 5
对于另外 30%30\% 的数据,base=2base=2
对于 100%100\% 的数据,1xn1001\leq x\leq n\leq1001mn(n1)21\leq m\leq \frac{n(n-1)}{2}q200q\leq 2000fi,02500\leq f_{i,0}\leq 2^{50}0d500\leq d\leq 50 且相同进制下 dd 值不重复,base10base\leq 10basebase 为一个质数。