Flower 为 Gellyfish 提供了 $$$[0, 1, \ldots, n-1]$$$ 的两种排列$$$^{\text{∗}}$$$:$$$p_0, p_1, \ldots, p_{n-1}$$$ 和 $$$q_0, q_1, \ldots, q_{n-1}$$$。
现在Gellyfish想要通过以下方法计算一个数组$$$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$$$。
示例
输入复制
330 2 11 2 050 1 2 3 44 3 2 1 0105 8 9 3 4 0 2 7 1 69 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$$$