406964: GYM102625 J RD Bhaiya and his new token system

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. RD Bhaiya and his new token systemtime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

RD Bhaiya came up with a new digital token system to secure the token numbers for all the customers. The token system is such that whenever he wants to generate some new tokens, he will feed a number into his token machine. The machine will store that number in it, if not already stored.

But these numbers are not the actual token numbers. The actual set of token numbers are the numbers obtained by taking the exclusive-OR ( or XOR $$$\oplus$$$ ) operation of all the subsets of the numbers stored in the machine (the subset may be empty). Now when the customers will reach the shop, they will tell the position of their token number, if all the unique token numbers generated till now, are arranged in increasing order. (This position is known to all the customers via a mobile app, which updates the details as and when the token numbers are updated). So, RD Bhaiya wants to know their actual token number from this position.

When a new customer asks for a token, RD Bhaiya may feed a new number into the machine, so as to increase the number of tokens.

Input

The first line of input contains one integer, $$$q$$$ ( $$$1 \leq q \leq 10^6$$$ ), the number of queries.

Next $$$q$$$ lines contain two integers $$$p$$$ and $$$n$$$, where $$$p$$$ ( $$$1 \leq p \leq 2$$$ ) is query type.

If $$$p=1$$$, $$$n$$$ ($$$1 \leq n \leq 10^9$$$) represents the number that RD Bhaiya feeds into the token machine.

If $$$p=2$$$, $$$n$$$ represents the position of the token and $$$1 \leq n \leq$$$ number of unique token numbers

Output

For the first type of queries don't output anything.

For the second type of queries, output the token number of that customer.

ExampleInput
14
2 1
1 1
2 1
2 2
1 2
2 1
2 2
2 3
2 4
1 3
2 1
2 2
2 3
2 4
Output
0
0
1
0
1
2
3
0
1
2
3
Note

Note 1: XOR of an empty subset is 0

Note 2: XOR of a singleton subset is the number present in the subset itself.

加入题单

上一题 下一题 算法标签: