2 seconds
256 megabytes
standard input
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 (1≤i≤q1≤�≤�), for each j� (1≤j≤n1≤�≤�), such that aj�� is divisible by 2xi2��, you add 2xi−12��−1 to aj��. Note that xi�� (1≤xi≤301≤��≤30) is a positive integer not exceeding 30.
After all modification queries, you need to output the final array.
The first line contains a single integer t� (1≤t≤1041≤�≤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� (1≤n,q≤1051≤�,�≤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� (1≤ai≤1091≤��≤109).
The third line of each test case contains q� integers x1,x2,x3,…,xq�1,�2,�3,…,�� — the elements of the array x� (1≤xi≤301≤��≤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 2⋅1052⋅105.
For each test case, output the array after all of the modification queries.
1 2 3 6 6 7 10 14 38 58 6 3 3 3 3 3 3 1 3 7 11 19
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].