Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shopping

Limits: 1s, 512 MB

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 upto 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?

Input

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.

Output

For each query, out the minimum amount of gifts you can get.

Samples

InputOutput
4
1 3 6 10
3
1 5 10
3
1
4
7
1
7
20

Author
  • nfssdq's Avatar

    nfssdq

    Nafis was a student of Jahangirnagar University, a die-hard programming contestant. His team became the champion in ACM-ICPC Dhaka Regional 2015. He participated in the 39th and 40th ACM-ICPC World Finals.
Discussion
Submit

Login to submit