Пусть $$$\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$$$. Можно доказать, что ответ всегда существует. Если существует несколько ответов, вы можете вывести любой из них.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых положительных числа $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) и $$$k$$$ ($$$1\le k\le 10^9$$$), обозначающих длину массива и количество раз выполнения функции $$$f$$$.
Вторая строка каждого набора входных данных содержит массив $$$b_1, b_2, \ldots, b_n$$$ ($$$0\le b_i < 998\,244\,353$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите одну строку, содержащую корректный массив $$$a$$$ длины $$$n$$$.
28 11 2 1 4 1 2 1 86 21 4 3 17 5 16
1 1 1 1 1 1 1 1 1 2 3 4 5 6
Из первого набора входных данных видно, что $$$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]$$$.
| Codeforces Round 942 (Div. 1) |
|---|
| Закончено |
