Пропонується в цій задачі реалізувати перемноження двох многочленів за відомим модулем \( MOD = 998 \, 244 \, 353 \). Використовуючи написану вами в цій задачі функцію, ви зможете здавати без проблем більшість завдань із комбінаторики, в якій потрібна ФФТ.

Формат вхідних даних

У першому рядку міститься ціле число \(n\) (\(0 \leq n \leq 18\)).

У другому рядку знаходиться \(2^n\) цілих чисел \(a_0, a_1, \ldots, a_{2^n-1}\) (\(0 \leq a_i < MOD - 1)\). Перший многочлен для перемноження \(A(x) = \sum\limits_{i=0}^{2^n-1} {a_i x^i}\).

У другому рядку знаходиться \(2^n\) цілих чисел \(b_0, b_1, \ldots, b_{2^n-1}\) (\(0 \leq b_i < MOD - 1)\). Другий многочлен для перемноження \(B(x) = \sum\limits_{i=0}^{2^n-1} {b_i x^i}\).

Формат вихідних даних

Нехай многочлен \( C (x) = A (x) \cdot B (x) \). Усі коефіцієнти при перемноженні беруться за модулем \(MOD\). Тоді напишемо, що \(C(x) = \sum\limits_{i=0}^{2^{n+1}-1} {c_i x^i}\). Виведіть \(c_0, c_1, \ldots, c_{2^{n+1}-1}\).

Приклад вхідних даних

1
1 1
1 1

Приклад вихідних даних

1 2 1 0