该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Orange有很多朋友，他们在寒假都打算来湖南旅游，由于湖南的菜以香辣味闻名，因此他们都想吃比较辣的食物来感受湘菜的文化。

我们假设湖南的所有湘菜馆分布在一个 $n$ 个节点 $m$ 条边的无向无权图上。每个湘菜馆有一个辣度 $w_i$。

现在有 $q$ 个朋友来吃湘菜，每个朋友各有一个辣度忍耐值 $L_i$，他们会向Orange询问距离他所在的节点 $u$ 最近的辣度不超过 $L_i$ 的湘菜馆到他所在位置的^距离。你需要帮助Orange回答每个朋友的询问。如果不存在满足的湘菜馆，则输出 -1。

形式化的说，你需要在一个具有 $n$ 个点 $m$ 条边且每个点的点权为 $w_i$ 的无项无权图上回答 $q$ 次询问：每次给出 $u$ 和 $L_i$，求出距离 $u$ 最近的满足 $w_v \le L_i$ 的点 $v$ 到点 $u$ 的距离或报告不存在。

^:我们这里定义距离为两点之间由最少的边构成的路径的边的数量。

Format

Input

输入第1行为2个整数 $n$ 和 $m$，表示图的点数和边数。

接下来1行，共 $n$ 个整数 $w_i$，表示每个湘菜馆的辣度。

接下来 $m$ 行，每行两个整数 $u,v$，表示一条边。

接下来1行，输入一个整数 $q$，表示询问次数。

接下来 $m$ 行，每行两个整数 $u, L_i$，表示一次询问。

数据范围

$1 \le n, m \le 10^5$

$1 \le w_i, L_i \le 500$

$1 \le q \le 10^5$

$1 \le u \le n$

存在 $50\%$ 的数据可以用 $O(n^2)$ 的算法通过。

Output

对于每个询问，输出一行表示答案。

Samples

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

-1
2
1
1
0