1891B.md (2292B)
1 Source: https://codeforces.com/problemset/problem/1891/B 2 3 B. Deja Vu 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 There are $q$ modification. On the $i$-th modification ($1 \leq i \leq q$), for each $j$ ($1 \leq j \leq n$), such that $a_j$ is divisible by $2^{x_i}$, you add $2^{x_i-1}$ to $a_j$. Note that $x_i$ ($1 \leq x_i \leq 30$) is a positive integer not exceeding 30. 24 25 After all modification queries, you need to output the final array. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) β the number of test cases. The description of the test cases follows. 30 31 The first line of each test case contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^5$) βthe length of the array $a$ and the number of queries respectively. 32 33 The second line of each test case contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$ β the elements of the array $a$ ($1 \leq a_i \leq 10^9$). 34 35 The third line of each test case contains $q$ integers $x_1, x_2, x_3, \ldots, x_q$ β the elements of the array $x$ ($1 \leq x_i \leq 30$), which are the modification queries. 36 37 It is guaranteed that the sum of $n$ and the sum of $q$ across all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output the array after all of the modification queries. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 5 3 51 52 1 2 3 4 4 53 54 2 3 4 55 56 7 3 57 58 7 8 12 36 48 6 3 59 60 10 4 2 61 62 5 4 63 64 2 2 2 2 2 65 66 1 1 1 1 67 68 5 5 69 70 1 2 4 8 16 71 72 5 2 3 4 1 73 ``` 74 75 Output 76 77 ``` 78 1 2 3 6 6 79 7 10 14 38 58 6 3 80 3 3 3 3 3 81 1 3 7 11 19 82 ``` 83 84 Note 85 86 In the first test case, the first query will add $2$ to the integers in positions $4$ and $5$. After this addition, the array would be $[1, 2, 3, 6, 6]$. Other operations will not modify the array. 87 88 In the second test case, the first modification query does not change the array. The second modification query will add $8$ to the integer in position $5$, so that the array would look like this: $[7, 8, 12, 36, 56, 6, 3]$. The third modification query will add $2$ to the integers in positions $2, 3$, $4$ and $5$. The array would then look like this: $[7, 10, 14, 38, 58, 6, 3]$.