Problem Description

Translated from ROIR 2020 Day 2 T3. Банкомат, translated by ksyx.

You are developing an ATM with multiple denominations, called the Universal ATM. Specifically, there are $n$ kinds of banknotes with denominations $a_1,~a_2,~\ldots,~a_n$ sorted in increasing order, i.e. for $i>2$, $a_{i-1}<a_i$. In addition, it is guaranteed that $a_1=1$.

Suppose a customer wants to withdraw a total amount of $c$. Your ATM will distribute banknotes using the following algorithm: each time, choose the largest denomination such that the total amount given to the user after choosing it does not exceed $c$, until the total amount reaches $c$. Since there are banknotes of denomination $1$, we can see that this algorithm always finishes.

To evaluate the efficiency of this algorithm, you want to know, among all requests with total amount not exceeding $b$, what is the maximum number of banknotes that may be needed. Because business scenarios are different, you need to answer $q$ queries for $b_1,~b_2,~\ldots,~b_q$.

Your task is to write a program that, given the list of denominations, determines for different business scenarios the maximum number of banknotes that may be needed.

Input Format

The first line contains an integer $n$, the number of denominations.

The next line contains $n$ integers $a_i$.

The third line contains an integer $q$, the number of queries.

The next $q$ lines each contain an integer $b_i$.

Output Format

For each query, output two integers: the total amount withdrawn by the customer in the case where the number of banknotes is maximized, and the number of banknotes. If multiple withdrawal requests not exceeding the maximum total amount in the input correspond to this number of banknotes, output any one of them.

4
1 5 10 50
3
2
8
50

2 2
8 4
49 9

Hint

Sample 1 Explanation

One feasible solution for each query is as follows:

$2=1+1$, $8=5+1+1+1$, $49=10+10+10+10+5+1+1+1+1$.

Constraints

For $100\%$ of the testdata, $1\le n\le 2\times 10^5$, $1=a_1<a_2<\ldots<a_n\le10^{18}$, $1\le q\le 2\times 10^5$, $1\le b_i\le 10^{18}$.

Details of each subtask are as follows:

Translated by ChatGPT 5