给定一个包含 $n$ 个顶点和 $m$ 条边的有向图，当且仅当存在一条从顶点 $u$ 到顶点 $v$ 的路径时，称数对 $(u, v)$ 是“好的”。显然，数对 $(u, u)$ 也是好的。

一个好的数对 $(u, v)$ 的值等于 $u \oplus v$。这里的 $\oplus$ 指的是按位异或运算。

我们将进行 $Q$ 次查询。每次查询给定一个整数 $K$，请输出所有好的数对中第 $K$ 大的值。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 3$)，表示测试用例的数量。

对于每个测试用例： 第一行包含三个整数 $n$ ($1 \le n \le 50000$)，$m$ ($1 \le m \le 200000$) 和 $Q$ ($1 \le Q \le 10$)，分别表示图中的顶点数、边数以及查询次数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示一条从 $u$ 到 $v$ 的有向边。图中不包含重边。

接下来 $Q$ 行，每行包含一个整数 $K$ ($1 \le K \le 10^9$)。

保证答案一定存在。

输出格式

对于每个测试用例，输出所有好的数对中第 $K$ 大的值。

样例

输入 1

2
3 3 3
1 2
1 3
2 3
1
2
3
7 7 5
1 2
3 5
5 4
4 3
1 5
2 6
5 7
1
3
5
7
9

输出 1

3
2
1
7
7
6
5
4