CF702F.T-Shirts

The big consignment of t-shirts goes on sale in the shop before the beginning of the spring. In all n types of t-shirts go on sale. The t-shirt of the i-th type has two integer parameters — c__i and q__i, where c__i — is the price of the i-th type t-shirt, q__i — is the quality of the i-th type t-shirt. It should be assumed that the unlimited number of t-shirts of each type goes on sale in the shop, but in general the quality is not concerned with the price.

As predicted, k customers will come to the shop within the next month, the j-th customer will get ready to spend up to b__j on buying t-shirts.

All customers have the same strategy. First of all, the customer wants to buy the maximum possible number of the highest quality t-shirts, then to buy the maximum possible number of the highest quality t-shirts from residuary t-shirts and so on. At the same time among several same quality t-shirts the customer will buy one that is cheaper. The customers don't like the same t-shirts, so each customer will not buy more than one t-shirt of one type.

Determine the number of t-shirts which each customer will buy, if they use the described strategy. All customers act independently from each other, and the purchase of one does not affect the purchase of another.

大批T恤在春季开始前在商店促销。共有 $n$ 种类型的T恤参与促销。第 $i$ 种T恤有两个整数参数：$c_i$ 和 $q_i$，其中 $c_i$ 表示第 $i$ 种T恤的价格，$q_i$ 表示第 $i$ 种T恤的质量。假设每种T恤均有无限库存，但总体而言，质量与价格之间并无关联。

据预测，接下来一个月内将有 $k$ 位顾客光顾该商店，其中第 $j$ 位顾客最多愿意花费 $b_j$ 元购买T恤。

所有顾客均采用相同的购买策略：首先，顾客希望尽可能多地购买质量最高的T恤；然后，在剩余T恤中尽可能多地购买质量次高的T恤，依此类推。同时，若存在多个质量相同的T恤，顾客将优先选择价格更低者。此外，顾客不喜欢重复的T恤，因此每位顾客对每种类型的T恤至多购买一件。

请确定在上述策略下，每位顾客将购买多少件T恤。所有顾客相互独立行动，某位顾客的购买行为不会影响其他顾客的购买决策。

The first line contains the positive integer n (1 ≤ n ≤ 2·105) — the number of t-shirt types.

Each of the following n lines contains two integers c__i and q__i (1 ≤ c__i, q__i ≤ 109) — the price and the quality of the i-th type t-shirt.

The next line contains the positive integer k (1 ≤ k ≤ 2·105) — the number of the customers.

The next line contains k positive integers _b_1, _b_2, ..., b__k (1 ≤ b__j ≤ 109), where the j-th number is equal to the sum, which the j-th customer gets ready to spend on t-shirts.

第一行包含一个正整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 表示 T 恤的种类数。

接下来的 $n$ 行，每行包含两个整数 $c_i$ 和 $q_i$（$1 \leq c_i, q_i \leq 10^9$）—— 分别表示第 $i$ 种 T 恤的价格和质量。

下一行包含一个正整数 $k$（$1 \leq k \leq 2 \cdot 10^5$）—— 表示顾客的数量。

再下一行包含 $k$ 个正整数 $b_1, b_2, \dots, b_k$（$1 \leq b_j \leq 10^9$），其中第 $j$ 个数 $b_j$ 表示第 $j$ 位顾客愿意在 T 恤上花费的金额。

The first line of the input data should contain the sequence of k integers, where the i-th number should be equal to the number of t-shirts, which the i-th customer will buy.

输入数据的第一行应包含一个由 $k$ 个整数构成的序列，其中第 $i$ 个数应等于第 $i$ 位顾客将购买的 T 恤件数。

In the first example the first customer will buy the t-shirt of the second type, then the t-shirt of the first type. He will spend 10 and will not be able to buy the t-shirt of the third type because it costs 4, and the customer will owe only 3. The second customer will buy all three t-shirts (at first, the t-shirt of the second type, then the t-shirt of the first type, and then the t-shirt of the third type). He will spend all money on it.

在第一个例子中，第一位顾客将先购买第二种类型的T恤，再购买第一种类型的T恤，共花费10；由于第三种类型T恤的价格为4，而该顾客此时仅剩3，因此无法购买第三种类型的T恤。第二位顾客将购买全部三种T恤（顺序为：先买第二种类型，再买第一种类型，最后买第三种类型），并恰好花光所有钱。