C-取钱_牛客练习赛86

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

某个国家的货币体系里有 $\texttt{n}$ 种面值不同的纸币，从小到大面值分别是 $a_1,a_2,...,a_n$ ， $a_1=1$ 。

当取款人去 $\texttt{ATM}$ 机取款 $\texttt{c}$ 元的时候， $\texttt{ATM}$ 机按一种贪心的策略给取款人发放钞票，策略如下：

首先，已发放钞票的集合是空集，每一次 $\texttt{ATM}$ 机都会放一张当前可以放的最大面值的钞票进去，一直到集合里纸币面额等于 $\texttt{c}$ ，然后将集合里的纸币吐给取款人。

现在这个国家的公民觉得用钱把裤兜装的满满的会很有面子，但是他们又不想取出太多钱。现在他们问你：在最多取 $b_i$ 元的情况下，最多可以获得多少张纸币。

第一行一个正整数 $n$ ，表示钞票的面值数

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$ ，表示 $n$ 种钞票的面值

第三行一个正整数 $q$ ，表示公民询问的数量

接下来 $q$ 行每行一个整数 $b_i$

$1 \le n \le 2 \times 10^5$

$1 = a_1 < a_2 < ... < a_n \le 10^{18}$

$1 \le q \le 2 \times 10^5$

$1 \le b_i \le 10^{18}$

对于每个查询输出两个数字：取款的金额以及获得的纸币数量

若在不超过 $b_i$ 的情况下有多个金额取款获得的纸币数量都是最大值，输出任意一个金额即可

示例1

复制

复制

2 2
8 4
49 9