题目描述

神遗弃了祂的子民。

---

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

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

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

$$f_{x,j}=f_{y1,j-1}\oplus f_{y2,j-1}\oplus \cdot\cdot\cdot\oplus f_{yk,j-1} $$

其中 $j\ge 1$，$y_1,y_2,\cdots,y_k$ 是所有与 $x$ 号遗址直接相连的遗址，$\oplus$ 为 $base$ 进制下的不进位加法。

因为丰收女神陨落后留下了诅咒，进制 $base$ 并不是固定的。

戴里克会向“愚者”先生提 $q$ 个问题。每次他会给出三个数：询问点 $x$，进制 $base$，还有天数 $day$。

为了不让洛薇雅长老察觉，戴里克给出的 $day$ 经过加密。解密方法为：设上一次相同进制 $base$ 的询问解密后为 $last\_day$，本次询问给的数为 $d$，则当前 $day$ 值为 $last\_day+2^d$。$last\_day$ 初始值为 $0$。

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

作为“愚者”的虔诚信徒，你需要代替“愚者”先生回答戴里克， $base$ 进制下，$day$ 天后，$x$ 点的天气。

输入格式

第一行三个正整数 $n$，$m$ 和 $q$，分别代表点数，边数和询问数。
接下来一行 $n$ 个正整数 $f_{i,0}$。
接下来 $m$ 行，每行两个正整数 $x$ 和 $y$，代表 $x$ 和 $y$ 之间有一条无向边。
接下来 $q$ 行，每行三个整数 $x$，$base$，$d$。其中 $d$ 经过加密，解密方法题目描述里已给出。
所有输入均以十进制形式给出。

输出格式

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

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

数据规模与约定

共 $20$ 个测试点。
对于 $30\%$ 的数据，$n\leq 10$，$q\leq 10$，$d\leq 5$。
对于另外 $30\%$ 的数据，$base=2$。
对于 $100\%$ 的数据，$1\leq x\leq n\leq100$，$1\leq m\leq \frac{n(n-1)}{2}$，$q\leq 200$，$0\leq f_{i,0}\leq 2^{50}$，$0\leq d\leq 50$ 且相同进制下 $d$ 值不重复，$base\leq 10$ 且 $base$ 为一个质数。