给定一个长度为 $$$n$$$ 的数组 $$$a$$$,由正整数组成,以及一个长度为 $$$q$$$ 的数组 $$$x$$$,也由正整数组成。
有$$$q$$$修改。在第 $$$i$$$ 次修改 ($$$1 \leq i \leq q$$$) 中,对于每个 $$$j$$$ ($$$1 \leq j \leq n$$$),使得 $$$a_j$$$ 可被 $$$2^{x_i}$$$ 整除,将 $$$2^{x_i-1}$$$ 添加到 $$$a_j$$$。请注意,$$$x_i$$$ ($$$1 \leq x_i \leq 30$$$) 是不超过 30 的正整数。
所有修改查询后,需要输出最终的数组。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) ——分别是数组 $$$a$$$ 的长度和查询的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \ldots, a_n$$$ — 数组 $$$a$$$ 的元素 ($$$1 \leq a_i \leq 10^9$$$)。
每个测试用例的第三行包含 $$$q$$$ 整数 $$$x_1, x_2, x_3, \ldots, x_q$$$ — 数组 $$$x$$$ 的元素 ($$$1 \leq x_i \leq 30$$$),它们是修改查询。
保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在所有修改查询后输出数组。
示例
输入 #1
4 5 3 1 2 3 4 4 2 3 4 7 3 7 8 12 36 48 6 3 10 4 2 5 4 2 2 2 2 2 1 1 1 1 5 5 1 2 4 8 16 5 2 3 4 1
输出 #1
1 2 3 6 6 7 10 14 38 58 6 3 3 3 3 3 3 1 3 7 11 19
注意
在第一个测试用例中,第一个查询会将 $$$2$$$ 添加到位置 $$$4$$$ 和 $$$5$$$ 处的整数。添加之后,数组将是 $$$[1, 2, 3, 6, 6]$$$。其他操作不会修改数组。
在第二个测试用例中,第一个修改查询不会更改数组。第二个修改查询会将 $$$8$$$ 添加到位置 $$$5$$$ 处的整数,以便数组看起来像这样:$$$[7, 8, 12, 36, 56, 6, 3]$$$。第三个修改查询会将 $$$2$$$ 添加到位置 $$$2、3$$$、$$$4$$$ 和 $$$5$$$ 处的整数。该数组将如下所示:$$$[7, 10, 14, 38, 58, 6, 3]$$$。