ADAAPHID - Ada and Aphids


Ada the Ladybug breeds aphids. Whenever a new aphid is born, she assigns him an ID. She did that for long time but as she can't remember tha ID's she sometime made duplicates. She wanted to avoid such situation so she extended the ID to pair. She has also chosen a random number, which she assigned to aphid and then she made second integer of ID as sum of values of all aphids with ID lesser or equal to current ID (including current ID).

She wants to know the ID of each aphid. Please, read the input section carefully.

Input

The first line contains 1 ≤ Q ≤ 3*105 , number of aphids added.

Let L be the second integer of last aphid's ID (beggining with 0).

The next Q lines contains two numbers A, V, 0 ≤ A, V < 260, where A ⊕ L is the first integer of aphid's ID and V ⊕ L is the random number ( stands for XOR).

1 ≤ A ⊕ L < 260

1 ≤ V ⊕ L < 1000

Output

For each query print both number's of aphid's ID.

Example Input

7
1 1
3 3
4 0
3 2
5 6
13 13
19 19

Example Output

1 1
2 3
7 6
5 7
2 4
9 20
7 18

Input after XOR

7
1 1
2 2
7 3
5 4
2 1
9 9
7 7

hide comments
changyouren: 2021-10-03 14:51:49

TLE

andy489: 2021-08-31 00:35:22

I/O explained here:

(https://github.com/andy489/Fast_Algorithms_in_Data_Structures/blob/main/Treap%20(Cartesian%20Tree)/Problems/ADAAPHID%20%E2%80%93%20Ada%20and%20Aphids%20%E2%80%93%20IO%20explanation.pdf)

Last edit: 2021-08-31 00:35:43
theanshul: 2020-08-29 10:24:59

@daviddamian01: It could be because the A^L is not in int range. I was also getting WA in test case 15 but when I changed it to long long, it got AC.

Scape: 2020-06-05 01:20:53

@morass your problems are usually nice and fun to solve. But this was an abomination compared to the rest of your problems. Please fix the statement, it literally gave me a headache.

fahimcp495: 2020-06-01 06:58:18

problem statement is not so bad
nice problem

daviddamian01: 2020-05-15 23:41:36

My treap failed at test case 15 :(

helmib: 2020-03-30 17:34:18

Nice problem, but this must be the worst problem statement ever.

julkas: 2019-04-29 12:45:41

@Morass. Good problem. Thanks.

srafael_: 2018-07-16 15:33:14

treap making my day :)

shruti18: 2018-06-18 18:21:59

The problem statement is very unclear...


Added by:Morass
Date:2017-02-12
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All