给定三个长度均为 $N$ 的整数序列 $A$、$B$ 和 $C$。对于每个 $k = 1, 2, \dots, N$，求出以下式子的值，结果对 $998244353$ 取模：

$$\sum_{1 \le i \le N} \left( C_i \times \prod_{1 \le j \le k} (A_i + B_j) \right)$$

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 250000$)。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ($0 \le A_i < 998244353$)。 第三行包含 $N$ 个整数 $B_1, B_2, \dots, B_N$ ($0 \le B_i < 998244353$)。 第四行包含 $N$ 个整数 $C_1, C_2, \dots, C_N$ ($0 \le C_i < 998244353$)。

输出格式

对于每个 $k = 1, 2, \dots, N$，输出对应的答案。

样例

样例输入 1

3
1 2 3
4 5 6
7 8 9

样例输出 1

146 1050 8694