# [Solution] Deja Vu Solution codeforces

Deja Vu Solution codeforces
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a of length n, consisting of positive integers, and an array x of length q, also consisting of positive integers.

There are q modification. On the i-th modification (1iq1≤�≤�), for each j (1jn1≤�≤�), such that aj�� is divisible by 2xi2��, you add 2xi12��−1 to aj��Note that xi�� (1xi301≤��≤30) is a positive integer not exceeding 30.

After all modification queries, you need to output the final array.

Input

The first line contains a single integer t (1t1041≤�≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n and q (1n,q1051≤�,�≤105) —the length of the array a and the number of queries respectively.

The second line of each test case contains n integers a1,a2,a3,,an�1,�2,�3,…,�� — the elements of the array a (1ai1091≤��≤109).

The third line of each test case contains q integers x1,x2,x3,,xq�1,�2,�3,…,�� — the elements of the array x (1xi301≤��≤30), which are the modification queries.

It is guaranteed that the sum of n and the sum of q across all test cases does not exceed 21052⋅105.

Output

For each test case, output the array after all of the modification queries.

Example
input

Copy
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
output

Copy
1 2 3 6 6
7 10 14 38 58 6 3
3 3 3 3 3
1 3 7 11 19

Note

In the first test case, the first query will add 22 to the integers in positions 44 and 55. After this addition, the array would be [1,2,3,6,6][1,2,3,6,6]. Other operations will not modify the array.

In the second test case, the first modification query does not change the array. The second modification query will add 88 to the integer in position 55, so that the array would look like this: [7,8,12,36,56,6,3][7,8,12,36,56,6,3]. The third modification query will add 22 to the integers in positions 2,32,3 and 44. The array would then look like this: [7,10,14,38,58,6,3][7,10,14,38,58,6,3].