题目描述

IOI 的比赛开始了。Jsp 和 Rlc 坐在一个角落，这时他们听到了一个异样的声音 ……

接着他们发现自己收到了一封电子邮件：

我们在考场上放置了 $N$ 个炸弹。如果建立一个直线坐标系（数轴）的话，第 $i$ 个炸弹的坐标是 $X_i$，爆炸半径是 $R_i$，当一个炸弹爆炸时，如果另一个炸弹所在位置 $X_j$ 满足： $$ X_i-R_i\leq X_j\leq X_i+R_i $$ 那么，炸弹 $j$ 也会被引爆。

若 $i$ 和 $j$ 满足上述关系式，称 $i$ 能直接引爆 $j$。若 $i$ 不能直接引爆 $j$，但引爆 $i$ 会导致 $j$ 爆炸，则称 $i$ 能间接引爆 $j$。

我可以告诉你们，这些炸弹满足一个性质：若引爆炸弹 $A$ 会直接或间接地引爆炸弹 $B$，则引爆炸弹 $B$ 一定不会直接或间接地引爆炸弹 $A$。

有能耐就拆掉炸弹吧！记住，如果其它选手有所动作的话，后果你们应该知道！

吃惊的 Jsp 和 Rlc 开始了调（报）查（警）。之后，这些话被证实了。并且两人还发现了另一个性质：

定义炸弹 $A$ 到 $B$ 的“引爆距离”（用 $d(A,B)$ 表示）为最长的满足以下条件的序列 $a_1,a_2,...,a_n$ 的长度：

1. $a_i$ 互不相同，且为 $[1,N]$ 中的整数；
2. $ai$ 能直接引爆 $a{i+1}$；
3. $a_1=A,a_n=B$。

那么这个性质可以表述为：若 $d(A,B)=3$，$A$ 一定能直接引爆 $B$。

经过进一步研究，Rlc 发现最为安全的方法是这样：首先选出若干个关键炸弹安装监测器，然后慢慢拆除。

因为炸弹的某些特性，安装监测器的炸弹必须组成一个有序序列 $a_1,a_2,...,a_n$，且满足：

1. $a_i$ 互不相同，且为 $[1,N]$ 中的整数。
2. $ai$ 能直接或间接引爆 $a{i+1}$。

Rlc 设计了一个衡量监测器安装方案的安全程度的方法：

首先可以测出每个炸弹的特征值 $vi$。
那么监测器安装方案的安全程度为：$\sum{i=1}^{n-1}F(v_{ai},v{a_{i+1}})$，其中 $F(x,y)=(x\oplus y+xy)\bmod 998244353$（$\oplus$ 表示二进制按位异或，本题中按位异或的优先级高于乘法和加法）。

现在她想知道，对于 $[1,N]$ 中的每个整数 $i$，如果她安装监测器的最后一个炸弹是 $i$（即 $a_n=i$），安全程度最大是多少。

请特别注意，题面中大写的 $N$ 表示炸弹总数，小写 $n$ 表示上下文中的序列长度，请勿混淆。

输入格式

第一行一个整数 $N$ 表示炸弹个数。
第二行 $N$ 个整数 $X_1,X_2,...,X_N$，表示炸弹的坐标。
第三行 $N$ 个整数 $R_1,R_2,...,R_N$，表示炸弹的爆炸半径。
第四行 $N$ 个整数 $v_1,v_2,...,v_N$，表示炸弹的特征值。

输出格式

输出 $N$ 行，每行一个整数，第 $i$ 行表示拆除的最后一个炸弹是 $i$ 时的最大安全程度。

样例

input

6
-3 -2 0 2 3 4
0 1 4 1 0 1
4 1 3 4 2 0

output

19
5
0
19
33
3

以 $1$ 结尾的最优监测器安装序列：$3,1$ 以 $2$ 结尾的最优监测器安装序列：$3,2$ 以 $3$ 结尾的最优监测器安装序列：$3$ 以 $4$ 结尾的最优监测器安装序列：$3,4$ 以 $5$ 结尾的最优监测器安装序列：$3,4,5$ 以 $6$ 结尾的最优监测器安装序列：$3,6$

数据范围与提示

对于所有数据，$1\leq N\leq 3\times 10^5,0\leq v_i<998244353,0\leq R_i\leq 10^{18},|X_i|\leq 10^{18}$。

请特别注意，题面中大写的 $N$ 表示炸弹总数，小写 $n$ 表示上下文中的序列长度，请勿混淆。