Description

小 A 在四处游历的时候，发现了一个花园，这个花园是由 n 个亭子和 m 条无向小路组成的。每个亭子有 $c_i$ 种类的花无限朵；每条小路连接两个亭子 $u_i$ 与 $v_i$，且每条小路有一个长度 $l_i$。小 A 想要逛逛这个花园，于是他制定了 $q$ 次旅行计划。

每次他从花园的一个亭子 $a_i$ 出发，由于他不想走太远的小路，于是在这次旅行计划中，他只能走长度不超过 $b_i$ 的小路。他将到达所有他能够到达的亭子，并在每个到达过的亭子采一朵花（同一个亭子只采一束花）。

小 A 想知道，每次旅行结束后，采摘的哪种花最多？如果有若干种花一样多，那么输出种类编号最小的那一种。小 A 还要继续他的旅程，于是他把这个事情交给了你。

特殊地，由于小 A 需要依赖上次旅行计划的结果来制定下次旅行计划，所以你可能需要实时回答他的问题。

Format

Input

第一行，三个数 $n, m, type$，表示有 $n$ 个亭子和 $m$ 条无向小路，$type$ 表示数据种类；

第二行，$n$ 个数 $c_1, c_2, \cdots, c_n$，表示每个亭子花的种类；接下来 m 行，每行三个数 $u_i, v_i, l_i$，分别表示小路连接的两个亭子和小路的长度；

接下来一行，一个数 $q$，表示小 A 的旅行计划总数；

接下来 $q$ 行，每行两个数 $a_i, b_i$，描述一次旅行计划，分别表示旅行计划的起点和旅行计划中，对于可经过的小路长度的限制。 注意：当 $type = 2$ 时，设上一个询问的答案为 $lastans$，你需要将输入的 $a_i, b_i$ 进行如下操作后得到真实的 $a_i^*, b_i^*$，其中 $\oplus$ 表示按位异或操作。

$$a_i^* = a_i \oplus lastans, b_i^* = b_i \oplus lastans $$

初始时，$lastans = 0$。

Output

对于每个询问，输出一行，一个数，表示手上数量最多的花的种类。如果有若干种花一样多，那么输出种类编号最小的那一种。

Samples

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

2 1 3 1

见下发文件

见下发文件

样例解释

真正询问的 $(a_i, b_i)$ 为： ${(1, 1), (2, 2), (4, 4), (5, 8)}$。

Limitation

对于 30% 的数据，$1 \leq n, m, q \leq 10^3$；

对于 100% 的数据，$1 \leq n \leq 131071, 1 \leq m, q \leq 2 \cdot 10^5$，$1 \leq u_i, v_i, c_i, a_i \leq n$，$1 \leq l_i, b_i \leq 10^6$。

有 45% 的数据分散在各档次数据中，满足 type = 1；其余 55% 数据 type = 2。

有 25% 的数据分散在各档次数据中，满足 $1 \leq c_i \leq 20$。