IOI 的比赛开始了。Jsp 和 Rlc 坐在一个角落，这时他们听到了一个异样的声音 ……
接着他们发现自己收到了一封电子邮件：
我们在考场上放置了 个炸弹。如果建立一个直线坐标系（数轴）的话，第 个炸弹的坐标是 ，爆炸半径是 ，当一个炸弹爆炸时，如果另一个炸弹所在位置 满足：
那么，炸弹 也会被引爆。
若 和 满足上述关系式，称 能直接引爆 。若 不能直接引爆 ，但引爆 会导致 爆炸，则称 能间接引爆 。
我可以告诉你们，这些炸弹满足一个性质：若引爆炸弹 会直接或间接地引爆炸弹 ，则引爆炸弹 一定不会直接或间接地引爆炸弹 。
有能耐就拆掉炸弹吧！记住，如果其它选手有所动作的话，后果你们应该知道！
吃惊的 Jsp 和 Rlc 开始了调（报）查（警）。之后，这些话被证实了。并且两人还发现了另一个性质：
定义炸弹 到 的“引爆距离”（用 表示）为最长的满足以下条件的序列 的长度：
那么这个性质可以表述为：若 ， 一定能直接引爆 。
经过进一步研究，Rlc 发现最为安全的方法是这样：首先选出若干个关键炸弹安装监测器，然后慢慢拆除。
因为炸弹的某些特性，安装监测器的炸弹必须组成一个有序序列 ，且满足：
Rlc 设计了一个衡量监测器安装方案的安全程度的方法：
首先可以测出每个炸弹的特征值 。
那么监测器安装方案的安全程度为：，其中 （ 表示二进制按位异或，本题中按位异或的优先级高于乘法和加法）。
现在她想知道，对于 中的每个整数 ，如果她安装监测器的最后一个炸弹是 （即 ），安全程度最大是多少。
请特别注意，题面中大写的 表示炸弹总数，小写 表示上下文中的序列长度，请勿混淆。
第一行一个整数 表示炸弹个数。
第二行 个整数 ，表示炸弹的坐标。
第三行 个整数 ，表示炸弹的爆炸半径。
第四行 个整数 ，表示炸弹的特征值。
输出 行，每行一个整数，第 行表示拆除的最后一个炸弹是 时的最大安全程度。
6
-3 -2 0 2 3 4
0 1 4 1 0 1
4 1 3 4 2 0
19
5
0
19
33
3
以 结尾的最优监测器安装序列：
以 结尾的最优监测器安装序列：
以 结尾的最优监测器安装序列：
以 结尾的最优监测器安装序列：
以 结尾的最优监测器安装序列：
以 结尾的最优监测器安装序列：
对于所有数据，。
请特别注意，题面中大写的 表示炸弹总数，小写 表示上下文中的序列长度，请勿混淆。
| Subtask # | 分值 | 的限制 | 的限制 | 的限制 |
|---|---|---|---|---|
| 1 | 无 | 无 | ||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 | ||||
| 6 | 无 | |||
| 7 | 无 |