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
srafael_: 2018-07-16 15:33:14

treap making my day :)

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

The problem statement is very unclear...

Lovro Puzar: 2018-02-20 16:54:09

I found the problem statement very difficult to understand.

The task is: for the i-th aphid with input (A[i], V[i]) after xor, the first part of the ID is A[i], the second part of the ID is equal to sum(V[k] for k <= i and A[k] <= A[i]).

The problem statement sounds like we will be tracking the two parts of the ID for each aphid, and the "random number" (V in the input for each aphid) is just used to generate the second part. (Instead, the "random number" V is tracked while the second part of the ID is just printed for each aphid.)

Last edit: 2018-02-21 05:42:17
mahmud2690: 2018-01-09 17:56:56

Can you please show how you generate all those numbers step-by-step? I can not get 20 at the 6th step.

Last edit: 2018-01-10 08:25:24
morass: 2017-12-19 10:36:50

@mahmud2690: Good day to you. This just means that every query has to by XORed by last answer to obtain real query. Good Luck!

mahmud2690: 2017-12-10 16:57:08

Can you explain how you generated those ids? I am unable to understand "Input after XOR" section...

morass: 2017-02-23 12:46:51

@[Rampage] Blue.Mary: Sorry for bad explanation. The "value" refers to the "She chosen a random number" part of text, which is second integer of input.

Have Nice Day ^_^

[Rampage] Blue.Mary: 2017-02-23 12:41:37

"she made second integer of ID as sum of vallues of all aphids with ID lesser or equal to current ID (including current ID)."

What does "value" mean? First integer or second integer or something else?

Last edit: 2017-02-23 13:09:53

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