Statement

This is supposed to be Problem C

Ninetail is a fox girl. She has a huge family. In fact, there are 1e18 foxes in her family. They are numbered from 1 to 1e18. The Fox #1 is the oldest and the #1e18 is the youngest.

The oldest fox, Miltail asks Ninetail for a favor because she is the only one who goes to school with human beings. Miltail wants to maintain a billboard for all the foxes's tails. It should have the support of following operations:

1. Operation renshuu <x> <y>: this will set the number of tails of the Fox #x to Y.

2. Operation shitsumon <x>: this should tell the print the number of tails of the Fox #x

3. Operation gisei <x>: a ceremony of foxes is held. For each fox Fox #i cuts down all its tails and gives it to #(i+x) (ie. right shift by x) If fox #(i+x) doesn't exist, his tails will be given to the god.

4. Operation shukufuku <x>: a spell is cast so that every fox will get another X tails.

Initially no foxes have tails. Please help implement the billboard system.

Input

The first line contains Q.

Then Q lines, each line contains one operation.

Output

For each operation 2, print the answer

Examples

Input

8
renshuu 1 2
renshuu 2 3
gisei 2
shukufuku 2
shitsumon 1
shitsumon 2
shitsumon 3
shitsumon 4

Output

2
2
4
5

Explain

Initial Tails for Fox #1 to #5 {0,0,0,0,0}

1. {2,0,0,0,0}
2. {2,3,0,0,0}
3. {0,0,2,3,0}
4. {0,0,4,5,0}

Constraints

$1\leq Q\leq 10^5$

All input numbers X: $1\leq X\leq 10^9$

50 pts will be awarded if you solved $1\leq Q\leq 10^3$