승현이와 승현이

석환나라에는 조승현이라는 이름을 가진 사람이 두 명 있다. 헷갈리니 한 명은 조승현13, 다른 한 명은 조승현16이라고 부르자. 둘은 서로의 존재를 모르고 지내다가 얼마 전 뉴스를 보고 알게 되었다. 자기와 이름이 같은 사람이 있다는 사실이 신기했던 둘은 연락처를 알아내 서로 연락하는 사이가 되었다.

어느 날 둘은 상대방이 사는 도시가 궁금해졌다. 전화로 서로의 도시를 설명하다 지친 둘은 결국 상대방의 도시로 여행을 가기로 했다.

석환나라는 $N$개의 도시로 이루어져 있고, 도시에는 1번부터 $N$번까지 번호가 붙어 있다. 도시 사이에는 도로가 $M$개 있다. 도로 하나는 서로 다른 두 도시를 잇고 양방향으로 다닐 수 있다. 어느 도시에서 출발하든 도로를 적당히 거쳐 나머지 모든 도시에 도착할 수 있음이 보장된다.

지금 조승현13은 $S$번 도시에 있고 조승현16은 $E$번 도시에 산다. 둘은 상대방에게 자기 도시로 오는 길을 알려주려고 전화를 계속 연결한 채 다음과 같이 여행한다.

1. 0일차에 조승현13은 $S$번 도시에, 조승현16은 $E$번 도시에 있다.
2. $i$일차($i \ge 0$) 아침에 둘은 전화로 오늘 누가 움직일지 정한다. 하루에 둘 중 한 명만 움직일 수 있다.
3. 움직이기로 한 사람은 지금 있는 도시에 연결된 도로 하나를 골라 그 도로를 따라 반대편 도시로 이동한다. 이 이동은 해가 지기 전에 언제나 끝난다.
4. $i$일차에 해가 진 뒤 둘은 다시 전화해 서로 무사한지 확인한다.
5. 확인한 직후 조승현13이 $E$번 도시에, 조승현16이 $S$번 도시에 있으면 여행을 끝낸다. 그렇지 않으면 숙소에서 자고 일어나 2번으로 돌아가 반복한다.

전화를 하려면 각자 가진 전화기가 일정 수준 이상의 무선 신호 출력을 낼 수 있어야 한다. 도시 $i$마다 무선 신호가 잘 퍼지는 정도를 나타내는 양의 정수 $C_i$가 있고, 도시 $a$와 도시 $b$ 사이에서 통화하려면 전화기가 $C_a \times C_b$ 이상의 출력을 낼 수 있어야 한다. 이상한 일이지만 두 사람이 같은 도시 안에 있어도 이 규칙은 그대로 적용된다.

두 조승현은 여행을 시작하기 전에 똑같은 전화기를 하나씩 사서 여행이 끝날 때까지 그 전화기만 쓴다. 전화기 가격은 전화기가 낼 수 있는 출력에 비례하므로, 어떻게 여행하느냐에 따라 필요한 전화기 가격이 달라진다. $S$와 $E$가 주어질 때, 여행을 무사히 마치는 데 필요한 전화기 출력의 최솟값을 구해 두 조승현을 만족시켜 주자.

입력은 테스트 케이스 하나로 이루어진다.

첫째 줄에 도시의 수 $N$($2 \le N \le 500$)과 도로의 수 $M$($1 \le M \le 3000$)이 주어진다.

둘째 줄에 정수 $N$개가 주어진다. $i$번째 정수는 $i$번 도시의 무선 신호 상수 $C_i$($1 \le C_i \le 40000$)다.

이후 $M$개 줄에 정수 두 개 $a$, $b$($1 \le a, b \le N$, $a \ne b$)가 공백으로 구분되어 주어진다. 도시 $a$와 도시 $b$를 잇는 도로가 있다는 뜻이다.

그다음 줄에 질문의 수 $Q$($1 \le Q \le \binom{N}{2}$)가 주어진다. 이후 $Q$개 줄에 정수 두 개 $S$, $E$($1 \le S, E \le N$, $S \ne E$)가 공백으로 구분되어 주어진다. 처음에 조승현13이 $S$번 도시에, 조승현16이 $E$번 도시에 있는 상황을 뜻한다.

$Q$개 줄에 걸쳐 각 질문의 답을 주어진 순서대로 출력한다. $i$번째 줄에는 $i$번째 질문에서 여행을 무사히 마치는 데 필요한 전화기 출력의 최솟값을 출력한다.