B. Гелифиш и гипсофила
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Флауэр дает Гелифишу две перестановки$$$^{\text{∗}}$$$ массива $$$[0, 1, \ldots, n-1]$$$: $$$p_0, p_1, \ldots, p_{n-1}$$$ и $$$q_0, q_1, \ldots, q_{n-1}$$$.

Теперь Гелифиш хочет вычислить массив $$$r_0,r_1,\ldots,r_{n-1}$$$ следующим образом:

  • Для всех $$$i$$$ ($$$0 \leq i \leq n-1$$$), $$$r_i = \max\limits_{j=0}^{i} \left(2^{p_j} + 2^{q_{i-j}} \right)$$$

Гелифиш очень ленива, поэтому вам нужно помочь ей вычислить элементы $$$r$$$.

Поскольку элементы $$$r$$$ могут быть очень большими, вам нужно вывести элементы $$$r$$$ по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Массив $$$b$$$ является перестановкой массива $$$a$$$, если $$$b$$$ состоит из элементов $$$a$$$ в произвольном порядке. Например, $$$[4,2,3,4]$$$ является перестановкой $$$[3,2,4,4]$$$, в то время как $$$[1,2,2]$$$ не является перестановкой $$$[1,2,3]$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_0, p_1, \ldots,p_{n-1}$$$ ($$$0 \leq p_i \lt n$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$q_0, q_1, \ldots,q_{n-1}$$$ ($$$0 \leq q_i \lt n$$$).

Гарантируется, что $$$p$$$ и $$$q$$$ являются перестановками массива $$$[0, 1, \ldots, n-1]$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке $$$n$$$ целых чисел $$$r_0, r_1, \ldots, r_{n-1}$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
3
0 2 1
1 2 0
5
0 1 2 3 4
4 3 2 1 0
10
5 8 9 3 4 0 2 7 1 6
9 5 1 4 0 3 2 8 7 6
Выходные данные
3 6 8 
17 18 20 24 32 
544 768 1024 544 528 528 516 640 516 768
Примечание

В первом наборе входных данных:

  • $$$r_0 = 2^{p_0} + 2^{q_0} = 1+2=3$$$
  • $$$r_1 = \max(2^{p_0} + 2^{q_1}, 2^{p_1} + 2^{q_0}) = \max(1+4, 4+2) = 6$$$
  • $$$r_2 = \max(2^{p_0} + 2^{q_2}, 2^{p_1}+2^{q_1}, 2^{p_2}+2^{q_0}) = (1+1, 4+4, 2+2) = 8$$$