← 返回题目列表

Codeforces · 1891/B

B. 似曾相识

中文机器翻译题面 查看原题

给定一个长度为 $$$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]$$$。