Gahui and ILGAM lake

시간 제한1초메모리 제한1024 MB

요약

고리 모양으로 배치된 4n개의 점 사이에 가중치 간선이 있고 네 점이 지하철역과 연결되어 있을 때, 각 질의 점에서 가장 가까운 역까지의 거리를 구한다.

난이도: 보통10점 중 4점
유형: 그래프, 최단 경로, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

Gahui often visited Konkuk University. Every time Gahui visited Konkuk University, she was surprised to see the huge ILGAM lake. It is bigger than several universities, such as Seokyung university and Hanseong university.

The lake has 4n points arranged like a ring, each numbered from 1 to 4n in counter-clockwise order. Each pair of adjacent points are connected in both directions. In other words:

If 1 ≤ a < 4n, point a is connected to point a+1 in both directions.
Point 1 is connected to point 4n in both directions.

Points n, 2n, 3n, and 4n are connected to 3 subway stations (Konkuk_Univ, Guui, Sejong_Univ) via roads. ILGAM lake is so big, the nearest station is different depending on the point. Gahui wants to know which subway station is the nearest to her current point. Please help Gahui.

[Picture 1] Roads and points when n = 2

입력

n is given in the first line.

In the next line, 4n numbers are given in the following format:

d1 d2 ... d4n

di is distance from point i to point i+1 when 1≤i<4n
d4n is distance from point 4n to point 1

And the information below is given on four lines.

dn,Konkuk_Univ dn,Guui dn,Sejong_Univ

d2n,Konkuk_Univ d2n,Guui d2n,Sejong_Univ

d3n,Konkuk_Univ d3n,Guui d3n,Sejong_Univ

d4n,Konkuk_Univ d4n,Guui d4n,Sejong_Univ

da,b is the distance between point a and station b.

In the next line, Q (number of questions) is given.

In the next Q lines, Q questions are given in the following format, one per line.

k
- What is the distance to the nearest station from point k?

출력

Print the answers to the questions, one per line.

제한

1 ≤ all distances in the problem ≤ 105
1 ≤ n ≤ 105
1 ≤ Q ≤ 105

예제2

예제 1

입력

1
1 1 1 1
999 999 999
888 888 888
1 2 3
888 888 888
1
1

예상 출력

예제 2

입력

1
100 90 80 1
999 999 999
888 888 888
777 777 777
1 1 1
1
1

예상 출력