There are two gift shops in the city. They are going to merge together to create a bigger company. You are in charge of the merger. The first shop has N different gift packages. The package numbered i costs i taka and gives some amount of gifts. The second shop does the same but it has M different packages. Both shops are progressive. Meaning you will always get more amount when you buy and the difference is increasing. Suppose if you can buy x units for i taka, y units for (i+1) taka and z units for (i+2) taka then z-y > y-x and x < y < z.
After merging, you can now sell up to N+M different packages. There is big queue in the line. Each customer will ask for a new package that cost exactly some amount of taka. Due to some regulations you can pick at most one package from each of the gift shops. What is the minimum amount of gift you can return to the customer, which cost him exactly the amount he asked?
First line of input contains an integer N (1 ≤ N ≤ 300000), the next line contains N integers, i'th integer will be the maximum amount of gifts you will get for i taka from the first shop.
The following line contains an integer M (1 ≤ M ≤ 300000), the next line contains M integers, i'th integer will be the maximum amount of gifts you will get for i taka from the second shop.
The following line is an integer Q (1 ≤ Q ≤ 300000). The next Q lines each contain an integer, the budget for that customer. (1 ≤ query integers ≤ N+M)
All other integers are positive and less than 1015.
For each query, out the minimum amount of gifts you can get.
| Input | Output |
|---|---|
4 1 3 6 10 3 1 5 10 3 1 4 7 | 1 7 20 |