차이 그래프

승현이에게 정점이 $N$개인 방향 그래프 $G$와 음이 아닌 정수로 이루어진 배열 $A[1], A[2], \dots, A[N-1]$이 있습니다. 정점에는 $0$ 이상 $N-1$ 이하의 번호가 붙어 있고, 간선마다 가중치가 있습니다. 처음에는 간선이 하나도 없어서 승현이는 그래프가 허전하다고 느꼈습니다. 그래서 다음과 같은 방법으로 간선을 잇기로 했습니다.

서로 다른 두 정점 $u$와 $v$ ($0 \le u, v < N$, $u \ne v$)에 대해

• $u > v$이고 $A[u-v]$가 양수이면, $u$에서 $v$로 향하는 가중치 $A[u-v]$인 간선을 추가합니다.
• $u < v$이고 $A[u-v+N]$이 양수이면, $u$에서 $v$로 향하는 가중치 $A[u-v+N]$인 간선을 추가합니다.

간선을 모두 추가한 뒤, 승현이는 한 정점에서 출발해 다른 정점에 도착하는 최단 경로의 길이를 구하려고 합니다.

첫째 줄에 그래프 $G$의 정점 수 $N$ ($5 \le N \le 2000$)이 주어집니다.

둘째 줄에 $A[1], A[2], \dots, A[N-1]$ ($0 \le A[1], A[2], \dots, A[N-1] \le 10000$)이 공백을 사이에 두고 주어집니다.

셋째 줄에 질의의 수 $Q$ ($1 \le Q \le 200000$)가 주어집니다.

이어지는 $Q$개 줄 가운데 $i$번째 줄 ($1 \le i \le Q$)에는 두 정수 $a_i$와 $b_i$ ($0 \le a_i, b_i < N$, $a_i \ne b_i$)가 공백을 사이에 두고 주어집니다.

각 질의마다 $a_i$번 정점에서 출발해 $b_i$번 정점에 도착하는 최단 경로의 길이를 입력에 주어진 순서대로 한 줄에 하나씩 출력합니다. 그러한 최단 경로가 없으면 $-1$을 출력합니다.