406390: GYM102394 G Game Store

Alice and Bob are playing a pretty old Nim game now. In this game, there are several piles of stones, where each pile may contain multiple stones. Two players take turns to remove stones. The player who can't take any legal moves first loses. In each move, the player can take one of the two possible moves below:

• Select a pile of stones, then remove $$$x$$$ stones from it, where $$$x\geq 1$$$.
• Select two piles of stones, then remove $$$x$$$ stones from one pile, and remove $$$y$$$ stones from the other pile, where $$$x,y\geq 1$$$. Note that $$$x$$$ and $$$y$$$ can be different.

Alice always takes moves first. Bob thinks it is unfair to him. To make the game look more "fair", Bob can choose any subset of piles and remove those piles before the game starts. Note that Bob can choose to not remove any piles, but he can't remove all the piles, because obviously it will cause Alice to lose.

Both Alice and Bob are masters in this game, so they always play optimally. They will play $$$n$$$ games in the next $$$n$$$ days, one game per day. There is a game store renting piles of stones. Initially, the store is empty. On the $$$i$$$-th day, the store will put a new set of stones on rent, which costs $$$b_i$$$ dollars per day and contains two same piles of stones, where each pile contains exactly $$$a_i$$$ stones. A set must be rented in its entirety, Alice can't choose to rent only one pile of stones from a set. On each day, Alice will rent some sets from the store, take all the rented sets back home, then play the game with Bob with all those sets, and finally return all the sets to the store (they will be available for rent again the next day). The player who loses pays for the cost of renting on that day.

You are a master in this game too. You notice that if Alice chooses piles optimally, she will never lose! Alice also discovers this fact, so she wants to make Bob pay as many dollars as possible. However, the number of sets in the store may be extremely large. Please write a program to help Alice rent sets optimally such that Alice can always win the game on each day, and Bob will pay as much as possible.

The input contains only a single case.

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 500\,000$$$), denoting the number of days. Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le i \le n, 1 \leq x_i,y_i \leq 10^{18}$$$), describing the new set put on rent on the $$$i$$$-th day. The input is encrypted in order to force online processing. The actual $$$a_i$$$ and $$$b_i$$$ are $$$x_i\oplus last$$$ and $$$y_i\oplus last$$$, where $$$last$$$ is the answer of the previous day and "$$$\oplus$$$" denotes bitwise exclusive-or. Note that for the first day, $$$last=0$$$. It is guaranteed that $$$1\leq a_i\leq 10^{18}$$$ and $$$1\leq b_i\leq 10^9$$$.

Print $$$n$$$ lines, where the $$$k$$$-th $$$(1\le k \le n)$$$ line contains a single integer, the maximum number of dollars that Bob needs to pay on the $$$k$$$-th day.

3
1 4
6 7
4 13

4
7
14

In the sample test, $$$a_1=1,b_1=4$$$; $$$a_2=2,b_2=3$$$ and $$$a_3=3,b_3=10$$$.