There are  cities in Berland, and they are connected by two railroads — the Main railroad and the Auxiliary railroad. Each city has two railway stations, one connected to the Main railroad (called the Main station), and the other connected to the Auxiliary railroad.

The railroads are identical in their structure. The Main railroad consists of  railroad segments; the -th railroad segment connects the Main station of the city  with the Main station of the city . Similarly, the Auxiliary railroad consists of  railroad segments; the -th railroad segment connects the Auxiliary station of the city  with the Auxiliary station of the city .

These railroads are used to transfer different goods and resources from one city to another. In particular, the Ministry of Energetics is interested in using these railroads to transfer coal.

The Ministry has estimated the following capabilities of the railroads:

• for every , at most  tons of coal per day can be transferred from the Main station  to the Main station  (only in this direction);
• for every , at most  tons of coal per day can be transferred from the Auxiliary station  to the Auxiliary station  (only in this direction);
• for every , at most  tons of coal per day can be transferred from the Main station  to the Auxiliary station , or in the opposite direction.

To analyze the capacity of the whole railroad network, the Ministry requires a software that would process and answer queries of the following format:

• calculate the maximum number of tons of coal that can be transferred per day from the Main station  to the Main station .

### Input Two Railroads solution codechef

The first line contains one integer  () — the number of cities.

The second line contains  integers  ().

The third line contains  integers  ().

The fourth line contains  integers  ().

The fifth line contains one integer  () — the number of queries.

Then  lines follow, the -th line contains two integers  and  () — the parameters of the -th query.

### Output Two Railroads solution codechef

Print  integers, where the -th integer should be the answer to the -th query, i. e. the maximum number of tons of coal that can be transferred per day from the Main station  to the Main station .

Example
input

### Copy Two Railroads solution codechef

5
3 4 7 4
8 5 3 5
10 5 3 4 10
4
1 4
1 2
3 4
2 4

output

### Copy Two Railroads solution codechef

9 8 10 9