ATM

A universal ATM is being developed that can work with any monetary system. Suppose a country's monetary system uses n banknote denominations a1, a2, ..., an. All denominations are distinct and listed in ascending order: if i > 2, then $a_{i-1} < a_i$, and $a_1 = 1$.

The ATM dispenses banknotes with the following greedy algorithm. Suppose a client requests an amount c. At first the set of dispensed banknotes is empty. At each step, the algorithm adds a banknote of the largest possible denomination such that the sum of denominations in the set does not exceed c. When the sum of denominations in the set equals c, the algorithm stops. Since a banknote with denomination $a_1 = 1$ exists, the algorithm always finishes in a finite number of steps.

To evaluate the efficiency of this algorithm, find the maximum number of banknotes that may need to be dispensed at once, when the largest amount that can be requested is b. Since the maximum amount may depend on a customer's service category, answer q queries for amounts b1, b2, ..., bq.

Write a program that, given the denominations and the largest requestable amount, determines the amount to request from the ATM so that the maximum number of banknotes is dispensed, and that number of banknotes.

The first line contains an integer n, the number of banknote denominations (1 ≤ n ≤ 200000).

The second line contains n distinct integers ai (1 = a1 < a2 < ... < an ≤ $10^{18}$).

The third line contains an integer q, the number of queries (1 ≤ q ≤ 200000).

Each of the next q lines contains one integer bi (1 ≤ bi ≤ $10^{18}$).

For each query, print two numbers: the amount to request so that the maximum number of banknotes is dispensed, and that number of banknotes.

If several amounts not exceeding the maximum give the maximum number of banknotes, print any of them.

In the example, 2 is dispensed as 1 + 1, 8 is dispensed as 5 + 1 + 1 + 1, and 49 is dispensed as 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1.