Island Trip

Jeongwoo travels for a living and for fun, and this time he plans to tour a group of islands. He picked $N$ islands, and $M$ bridges connect them, each bridge passable in both directions. Crossing one bridge counts as one move.

While reading the island heights printed on his map, Jeongwoo started wondering:

"Starting from island $A$ and crossing exactly $K$ bridges, what is the lowest height among the islands I can end up on?"

The same bridge may be crossed several times, and an island already visited may be visited again. Answer each of Jeongwoo's queries.

The first line contains the number of islands $N$ and the number of bridges $M$, separated by a space. ($2 \le N \le 100$, $1 \le M \le 10000$)

The second line contains the heights $H$ of islands 1 through $N$, separated by spaces. ($0 \le H \le 10000$)

Each of the next $M$ lines contains two integers $X$ and $Y$ describing one bridge, separated by a space. ($1 \le X, Y \le N$) It means island $X$ and island $Y$ are joined by a bridge passable in both directions. $X$ and $Y$ may be equal, and the same pair of islands may appear on several lines.

The next line contains the number of queries $T$. ($1 \le T \le 10000$)

Each of the following $T$ lines contains the starting island $A$ and the number of bridges to cross $K$, separated by a space. ($1 \le A \le N$, $1 \le K \le 500$)

For each query, print on its own line the lowest height among the islands reachable from island $A$ by crossing exactly $K$ bridges.

If no island is reachable with exactly $K$ crossings, print $-1$.