Пусть \(\operatorname{lowbit}(x)\) обозначает значение младшего двоичного бита \(x\), например, \(\operatorname{lowbit}(12)=4\), \(\operatorname{lowbit}(8)=8\).
Для массива \(a\) длины \(n\), если массив \(s\) длины \(n\) удовлетворяет условию \(s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353\) для всех \(k\), то \(s\) называется Деревом Фенвика массива \(a\). Обозначим его как \(s=f(a)\).
Для целого положительного числа \(k\) и массива \(a\), \(f^k(a)\) определяется следующим образом:
\(\) f^k(a)= \begin{cases} f(a)&\textrm{если }k=1\\ f(f^{k-1}(a))&\textrm{иначе.}\\ \end{cases} \(\)
Вам дан массив \(b\) длины \(n\) и целое положительное число \(k\). Найдите массив \(a\), который удовлетворяет условию \(0\le a_i < 998\,244\,353\) и \(f^k(a)=b\). Можно доказать, что ответ всегда существует. Если существует несколько ответов, вы можете вывести любой из них.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую корректный массив \(a\) длины \(n\).
Примечание
Из первого набора входных данных видно, что \(f^1([1,1,1,1,1,1,1,1])=[1,2,1,4,1,2,1,8]\).
Во втором наборе входных данных видно, что \(f^2([1,2,3,4,5,6])=f^1([1,3,3,10,5,11])=[1,4,3,17,5,16]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
8 1
1 2 1 4 1 2 1 8
6 2
1 4 3 17 5 16
|
1 1 1 1 1 1 1 1
1 2 3 4 5 6
|