熊猫先生有很多花园。对于每个花园 $i$，里面恰好有一朵颜色为 $c_i$ 的花。花园之间有许多道路相连，每条道路都有相应的代价。

熊猫先生喜欢在花园里走动，并尽可能多地采摘相同颜色的花。但有时他不想在代价过高的道路上花费时间。问题是，每次熊猫先生告诉你他开始采摘花朵的花园以及他能承受的最大代价 $w$（只有代价不超过 $w$ 的道路是可以通行的）。请找出熊猫先生能采摘到最多数量的花的颜色。如果有多种颜色数量相同，请找出颜色编号最小的那一种。

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例以两个整数 $N$ 和 $M$ 开头。$N$ 是花园的数量，$M$ 是道路的数量。

接下来一行包含 $N$ 个整数，表示花的颜色，第 $i$ 个数字是第 $i$ 个花园中花的颜色。

接下来的 $M$ 行描述了花园之间的道路。每行包含 3 个整数 $x, y, w$，表示在第 $x$ 个花园和第 $y$ 个花园之间有一条代价为 $w$ 的道路。

接下来是一行，包含一个整数 $Q$，表示询问的数量。接下来的 $Q$ 行，每行包含 2 个整数 $x, w$，表示熊猫先生从第 $x$ 个花园开始，他能承受的最大代价为 $w$。假设 last 是上一次询问的答案，则实际的 $x$ 和 $w$ 为输入值与 last 进行异或（XOR）运算的结果。对于每个测试用例的第一次询问，last = 0。

输出格式

对于每个测试用例，首先输出一行 “Case #x:”，其中 x 是测试用例的编号（从 1 开始）。

接下来的 $Q$ 行，每行包含一个整数，表示熊猫先生能采摘到最多数量的花的颜色编号。

数据范围

• $1 \le T \le 15$
• $1 \le N \le 10^5$
• $1 \le M, Q \le 2 \times 10^5$
• $1 \le x, y, c_i \le N$
• $1 \le w \le 10^6$
• 对于 60% 的测试用例，$N \le 5000$。

样例

样例输入 1

1
5 6
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

样例输出 1

Case #1:
2
1
3
1

说明

样例中的实际询问为 [(1, 1), (2, 2), (4, 4), (5, 8)]。