Дан массив \(a\) длины \(n\), состоящий из целых положительных чисел и массив \(x\) длины \(q\), также состоящий из целых положительных чисел.
Происходят \(q\) изменений. На \(i\)-м изменении (\(1 \leq i \leq q\)) для каждого \(j\) (\(1 \leq j \leq n\)), такого что \(a_j\) делится на \(2^{x_i}\), к \(a_j\) прибавляется \(2^{x_i-1}\). Обратите внимание, \(x_i\) (\(1 \leq x_i \leq 30\)) — целое положительное число, не превосходящее 30.
После всех запросов изменения нужно вывести итоговый массив.
Выходные данные
Для каждого набора входных данных выведите массив после всех изменений.
Примечание
В первом наборе входных данных первая операция изменения прибавит \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
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 2 3 6 6
7 10 14 38 58 6 3
3 3 3 3 3
1 3 7 11 19
|