似数佳对
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}给你四个长度为 n 的非负整数数组 a, b, c, d，下标从 1 开始。定义下标对 i, j \left(1 \leq i \lt j \leq n\right) 是「好的」，当且仅当 \left(a_i + \min\limits_{i \leq x \leq j} b_x \right) \leq c_j。
\hspace{15pt}对每个 1 \leq k \leq n，定义 {\rm ans}_k 为在所有「好的」下标对 i, j 中满足 j = k 的最大 d_i，特别地，当对于 k 不存在「好的」i 时，{\rm ans}_k = 0；且 {\rm ans}_0 = 0。

\hspace{15pt}题目强制在线，设当前读取到 a_i', b_i', c_i', d_i'，则 \begin{cases}a_i = a_i' \oplus {\rm ans}_{i - 1} \\ b_i = b_i' \oplus {\rm ans}_{i - 1} \\ c_i = c_i' \oplus {\rm ans}_{i - 1} \\ d_i = d_i' \oplus {\rm ans}_{i - 1}\end{cases}。

【名词解释】
\hspace{15pt}\oplus：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入描述:

\hspace{15pt}第一行输入一个正整数 n \left(1 \leq n \leq 5\cdot10^5\right)。
\hspace{15pt}此后 n 行，第 i 行输入四个非负整数 a_i', b_i', c_i', d_i'\left(0 \leq a_i', b_i', c_i', d_i' \lt 2^{30} \right)。且保证 1 \leq a_i, b_i, c_i, d_i \lt 10^9。

输出描述:

\hspace{15pt}在一行上输出 n 个非负整数 {\rm ans}_1, {\rm ans}_2, \dots, {\rm ans}_n。
示例1

输入

复制 
5
7 2 17 3
4 7 18 7
3 5 18 5
6 15 20 15
15 14 5 6

输出

复制 
0 3 7 7 0

备注:

\hspace{15pt}在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。