题目描述

现在正在开发一种万能自动取款机，它可以适用于任意货币系统。

设某个国家的货币系统中有 $n$ 种纸币，面额分别为：

所有面额互不相同，并按升序给出：

且保证：

自动取款机使用如下贪心算法发放纸币。

若客户请求金额为 $c$，初始时取款机准备发放的纸币集合为空。每一步，它会加入一张面额尽可能大的纸币，使得当前纸币总面额仍不超过 $c$。当纸币总面额等于 $c$ 时，算法停止。

因为存在面额为 $1$ 的纸币，所以算法一定会在有限步内结束。

为了评估这个贪心算法的效率，需要知道：如果客户最多可以请求金额 $b$，那么一次取款最多可能发放多少张纸币。

由于不同客户类别的最大可请求金额不同，你需要回答 $q$ 个询问 $b_1,b_2,\ldots,b_q$。

对于每个询问，请找出一个不超过 $b_i$ 的金额，使得自动取款机按上述贪心算法发放的纸币张数最多，并输出该金额以及对应张数。

输入格式

第一行包含整数 $n$，表示纸币面额种类数。

第二行包含 $n$ 个互不相同的整数 $a_i$，按升序给出。

第三行包含整数 $q$，表示询问个数。

接下来 $q$ 行，每行包含一个整数 $b_i$。

输出格式

对于每个询问，输出两个整数：

• 一个不超过 $b_i$ 的金额；
• 请求该金额时，贪心算法发放的最大纸币张数。

如果有多个金额都能达到最大纸币张数，输出任意一个即可。

数据范围

子任务

样例输入

4
1 5 10 50
3
2
8
50

样例输出

2 2
8 4
49 9

样例解释

在样例中：

• 请求 $2$ 时，取款机发放 $1+1$，共 $2$ 张；
• 请求 $8$ 时，取款机发放 $5+1+1+1$，共 $4$ 张；
• 请求 $49$ 时，取款机发放 $10+10+10+10+5+1+1+1+1$，共 $9$ 张。

题目 8. 海报