拍卖会有 $N$ 件商品在售。然而，拍卖方非常贪婪，商品的价格取决于你已经花费了多少钱。如果你已经花费了一定金额，拍卖方会按比例提高商品价格，因为你更有可能愿意以更高的价格购买该商品。

形式化地说，第 $i$ 件商品有两个参数 $M_i$ 和 $C_i$，该商品的价格为 $M_i \cdot X + C_i$，其中 $X$ 是你已经花费的总金额。

每件商品最多只能购买一次。你可以决定购买商品的顺序。

你需要回答 $Q$ 个如下形式的询问： * 如果你的预算为 $P_i$，你最多能购买多少件商品？

输入格式

• 第一行包含一个整数 $T$，表示测试用例的数量。
• 每个测试用例包含多行输入：
  • 第一行包含 2 个整数 $N$ 和 $Q$，分别表示商品数量和询问数量。
  • 第二行包含 $N$ 个整数 $M_1, M_2, \dots, M_N$，表示商品的线性系数。
  • 第三行包含 $N$ 个整数 $C_1, C_2, \dots, C_N$，表示商品的常数系数。
  • 接下来的 $Q$ 行，每行包含 1 个整数 $P_i$，表示预算询问。

输出格式

对于每个测试用例，按顺序输出 $Q$ 个整数，即对应询问的答案。

数据范围

• $1 \le T \le 10^4$
• $1 \le N, Q \le 2 \cdot 10^5$
• $0 \le M_i, C_i, P_i \le 10^9$
• 所有测试用例中 $N$ 的总和与 $Q$ 的总和均不超过 $2 \cdot 10^5$。

样例

样例输入 1

2
3 4
1 1000 0
3 6 4
2
6
7
19
6 6
0 0 1 1 2 3
0 1 0 2 3 4
0
1
8
15
3
10000

样例输出 1

0 1 2 3
2 3 4 5 4 6

说明

测试用例 1：以下是各询问的答案： 预算 2：无法购买任何商品。 预算 6：我们可以分别以价格 3, 6, 4 购买 3 件商品中的任意一件。但是，我们无法购买超过 1 件商品。 预算 7：首先，以价格 3 购买第 1 件商品，然后以价格 4 购买第 2 件商品。 预算 19：按以下顺序购买全部 3 件商品： $X = 0$，以价格 6 购买第 2 件商品。 $X = 6$，以价格 $1 \cdot 6 + 3 = 9$ 购买第 1 件商品。 $X = 15$，以价格 $0 \cdot 15 + 4 = 4$ 购买第 3 件商品。 我们总共花费 19 购买了全部 3 件商品。