섬 여행

여행이 취미이자 특기인 정우는 이번에 여러 섬을 돌아보기로 했다. 목적지로 잡은 섬은 모두 $N$개이고, 섬 사이에는 양방향으로 건널 수 있는 다리가 $M$개 놓여 있다. 다리를 한 번 건너는 것을 이동 한 번으로 센다.

지도에 적힌 섬의 높이를 보던 정우는 이런 궁금증이 생겼다.

"어떤 섬 $A$에서 출발해 다리를 정확히 $K$번 건넜을 때, 도착할 수 있는 섬 중에서 가장 낮은 섬의 높이는 얼마일까?"

같은 다리를 여러 번 건너도 되고, 이미 지나온 섬에 다시 들러도 된다. 정우의 질의마다 답을 구해 주자.

첫째 줄에 섬의 수 $N$과 다리의 수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 100$, $1 \le M \le 10000$)

둘째 줄에 1번 섬부터 $N$번 섬까지의 높이 $H$가 공백으로 구분되어 주어진다. ($0 \le H \le 10000$)

다음 $M$개의 줄에 다리 하나를 나타내는 두 정수 $X$와 $Y$가 공백으로 구분되어 주어진다. ($1 \le X, Y \le N$) $X$번 섬과 $Y$번 섬이 양방향 다리로 이어져 있다는 뜻이다. $X$와 $Y$가 같을 수 있고, 같은 두 섬을 잇는 다리가 여러 번 주어질 수도 있다.

그다음 줄에 질의의 수 $T$가 주어진다. ($1 \le T \le 10000$)

이어지는 $T$개의 줄에 출발하는 섬의 번호 $A$와 건너야 하는 다리의 수 $K$가 공백으로 구분되어 주어진다. ($1 \le A \le N$, $1 \le K \le 500$)

질의마다 한 줄에 하나씩, $A$번 섬에서 출발해 다리를 정확히 $K$번 건넜을 때 도착할 수 있는 섬의 높이 중 가장 낮은 값을 출력한다.

정확히 $K$번 건너서 도착할 수 있는 섬이 하나도 없으면 $-1$을 출력한다.