Sequence

对于两个序列 $a_1\dots a_n,b_1\dots b_m$。称序列二元组 $(a,b)$ 是好的当且仅当：

• 存在一条从 $(1,1)$ 到 $(n,m)$，每一步为某一维坐标增加 $1$ 的路径 $P$，使得 $\forall (x,y)\in P,a_x\le b_y$。

给定 $n,a_1,\dots,a_n,l_1\dots,l_n,r_1\dots r_n$。

对于每个 $k(1\le k\le n)$ 求出有多少个序列 $b_1\dots b_k$ 满足：

• $\forall 1\le i\le k,l_i\le b_i\le r_i$。
• $(a_1\dots a_n,b_1\dots b_k)$ 为好的序列二元组。

答案对 $998244353$ 取模。

输入格式

第一行，一个整数 $n$。

第二行，$n$ 个整数 $a_1,\dots,a_n$。

第三行，$n$ 个整数 $l_1,\dots,l_n$。

第四行，$n$ 个整数 $r_1,\dots,r_n$。

输出格式

一行，$n$ 个整数，第 $i$ 个整数表示 $k=i$ 时的答案。

样例 1

输入

2
1 2
1 1
2 2

输出

1 2

说明

$k=1$ 时路径 $(1,1)\to(2,1)$ 要求 $b_1\ge\max(a_1,a_2)=2$，只有 $b_1=2$，1 种；$k=2$ 时 $b\in[1,2]^2$ 中存在合法路径的有 $(1,2),(2,2)$，共 2 种。

样例 2

输入

3
1 1 1
1 1 1
3 3 3

输出

3 9 27

说明

$a$ 全为 $1$，任何 $b_i\ge 1$ 都满足 $a_x\le b_y$，必"好"。答案即前 $k$ 位取值数连乘 $3^k$：$3,9,27$

提示

对于 $100\%$ 的数据，$1\le n\le 5\times 10^3,1\le a_i\le 10^9,1\le l_i\le r_i\le 10^9$。

$\text{Subtask }1(10\%):n,a_i,l_i,r_i\le 5$。

$\text{Subtask }2(20\%):n,a_i,l_i,r_i\le 50$。

$\text{Subtask }3(30\%):n,a_i,l_i,r_i\le 500$。

$\text{Subtask }4(40\%):$ 无特殊限制。