Alice 和 Bob 正在玩一个古老的 Nim 游戏。在这个游戏中，有若干堆石子，每堆石子可能包含多个。两名玩家轮流移除石子。无法进行合法移动的玩家输掉游戏。在每一轮中，玩家可以执行以下两种操作之一：

• 选择一堆石子，移除其中的 $x$ 个石子，其中 $x \ge 1$。
• 选择两堆石子，从其中一堆移除 $x$ 个石子，并从另一堆移除 $y$ 个石子，其中 $x, y \ge 1$。注意 $x$ 和 $y$ 可以不同。

Alice 总是先手。Bob 认为这对他不公平。为了让游戏看起来更“公平”，Bob 可以在游戏开始前选择任意一个石子堆的子集并将这些堆移除。注意 Bob 可以选择不移除任何堆，但他不能移除所有堆，因为这显然会导致 Alice 输掉游戏。

Alice 和 Bob 都是这个游戏的高手，所以他们总是采取最优策略。在接下来的 $n$ 天里，他们每天会进行一场游戏。有一个出租石子堆的商店。最初，商店是空的。在第 $i$ 天，商店会放入一套新的石子供出租，这套石子每天的租金为 $b_i$ 美元，包含两堆完全相同的石子，每堆恰好有 $a_i$ 个石子。一套石子必须整体租用，Alice 不能选择只从一套中租用一堆石子。每天，Alice 会从商店租用一些套，把所有租来的套带回家，然后与 Bob 进行游戏，最后将所有套归还给商店（它们在第二天可以再次出租）。输掉游戏的玩家需要支付当天的租金。

你也是这个游戏的高手。你注意到，如果 Alice 选择石子堆的策略最优，她永远不会输！Alice 也发现了这一点，所以她想让 Bob 支付尽可能多的美元。然而，商店里的套数可能非常多。请编写一个程序，帮助 Alice 优化租用策略，使得 Alice 每天都能赢得游戏，且 Bob 支付的金额尽可能多。

输入格式

输入仅包含一组数据。

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示天数。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le i \le n, 1 \le x_i, y_i \le 10^{18}$)，描述第 $i$ 天放入出租的新套。输入经过加密以强制在线处理。实际的 $a_i$ 和 $b_i$ 分别为 $x_i \oplus \text{last}$ 和 $y_i \oplus \text{last}$，其中 $\text{last}$ 是前一天的答案，符号“$\oplus$”表示按位异或。注意对于第一天，$\text{last} = 0$。保证 $1 \le a_i \le 10^{18}$ 且 $1 \le b_i \le 10^9$。

输出格式

输出 $n$ 行，其中第 $k$ 行 ($1 \le k \le n$) 包含一个整数，表示 Bob 在第 $k$ 天需要支付的最大美元金额。

样例

样例输入 1

3
1 4
6 7
4 13

样例输出 1

4
7
14

说明

在样例测试中，$a_1 = 1, b_1 = 4; a_2 = 2, b_2 = 3$ 以及 $a_3 = 3, b_3 = 10$。