Seunghyun and Seunghyun

In the land of Seokhwan there are two people named Seunghyun. To tell them apart, call one of them Seunghyun 13 and the other Seunghyun 16. Neither knew the other existed until a news story told them so a while ago. Finding it strange that someone shared their name, they tracked down each other's number and started talking often.

One day each of them got curious about the city the other lives in. Describing a city over the phone wore them out, so they decided to travel to each other's city instead.

Seokhwan has $N$ cities numbered 1 through $N$, and $M$ roads run between them. One road joins two different cities and can be walked in both directions. Starting from any city, you can follow roads and reach every other city.

Seunghyun 13 is in city $S$ and Seunghyun 16 lives in city $E$. To explain the way to their own city, they keep the phone call up and travel like this.

1. On day 0, Seunghyun 13 is in city $S$ and Seunghyun 16 is in city $E$.
2. On the morning of day $i$ ($i \ge 0$) they call each other and decide who moves that day. Only one of them may move on a day.
3. The one who moves picks a road connected to the city they are in, follows it, and arrives at the city on the other end. This move always finishes before sunset.
4. After sunset on day $i$ they call again and check that both are safe.
5. If Seunghyun 13 is in city $E$ and Seunghyun 16 is in city $S$ right after that check, the trip ends. Otherwise they sleep at an inn and go back to step 2.

A call needs a phone that can put out at least a certain radio signal power. Each city $i$ has a positive integer $C_i$ that says how well radio signals spread there, and a call between city $a$ and city $b$ needs a phone that can put out at least $C_a \times C_b$. Strange as it is, the rule still applies when both of them are inside the same city.

Before the trip starts, the two Seunghyuns each buy one identical phone and use only that phone until the trip ends. A phone costs in proportion to the output it can put out, so the way they travel changes how expensive the phone has to be. Given $S$ and $E$, find the smallest phone output that lets them finish the trip safely.

The input is a single test case.

The first line has the number of cities $N$ ($2 \le N \le 500$) and the number of roads $M$ ($1 \le M \le 3000$).

The second line has $N$ integers. The $i$-th integer is $C_i$ ($1 \le C_i \le 40000$), the radio signal constant of city $i$.

Each of the next $M$ lines has two integers $a$ and $b$ ($1 \le a, b \le N$, $a \ne b$) separated by a space, meaning a road joins city $a$ and city $b$.

The next line has the number of questions $Q$ ($1 \le Q \le \binom{N}{2}$). Each of the next $Q$ lines has two integers $S$ and $E$ ($1 \le S, E \le N$, $S \ne E$) separated by a space, meaning Seunghyun 13 starts in city $S$ and Seunghyun 16 starts in city $E$.

Print the answers to the questions on $Q$ lines, in the given order. On the $i$-th line print the smallest phone output that finishes the trip safely for the $i$-th question.