成都共有 $n$ 家火锅店，编号为 $1$ 到 $n$，第 $i$ 家餐厅提供的火锅辣度为 $w_i$。辣度值越高表示口味越辣，辣度值越低则越温和（但即使是低辣度也需要小心）。

我们可以将这 $n$ 家餐厅视为无向图中的节点，图中有 $m$ 条边。现在有 $q$ 位游客想要尝试火锅。给定游客当前的位置以及他们能承受的最大辣度，你的任务是计算游客与他们能接受的最近餐厅之间的最短距离。

在本题中，路径的距离定义为路径中边的数量。

输入格式

每个测试文件仅包含一组测试数据。

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, m \le 10^5, 1 \le q \le 5 \times 10^5$)，分别表示餐厅数量、边数和游客数量。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 100$)，其中 $w_i$ 表示第 $i$ 家餐厅的辣度值。

接下来的 $m$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示连接餐厅 $u_i$ 和 $v_i$ 的一条边。

接下来的 $q$ 行，第 $i$ 行包含两个整数 $p_i$ 和 $a_i$ ($1 \le p_i \le n, 1 \le a_i \le 100$)，表示第 $i$ 位游客当前位于餐厅 $p_i$，且他能承受的最大辣度为 $a_i$。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 位游客与他能接受的最近餐厅之间的最短距离。如果不存在这样的餐厅，则输出 ‘-1’。

样例

样例输入 1

4 4 5
5 4 2 3
1 2
2 3
3 4
4 1
1 1
1 2
1 3
1 4
1 5

样例输出 1

-1
2
1
1
0