Problem Description

Snuke received an eagerly anticipated automatic MOD machine as a birthday present from his mom.

This automatic MOD machine is a device that displays the values of $ N $ variables $ A_{1}～A_{N} $. Snuke was playing with it by manipulating certain commands, but he got too excited and overused it, causing the machine to start behaving strangely.

The original automatic MOD machine has the following commands:

• Set: When executed, it sets the values of $ A_1～A_N $ to 0.
• Command 1: Input values $ p, v $. When this command is the $ i $th command since the last Set, it replaces all values in $ A_1～A_p $ that have a remainder of $ i $ or more when divided by $ i+v $ with the smallest multiple of $ i+v $ greater than the number.
• Command 2: Input value $ p $. This command outputs the value of $ A_p $.
• Command 3: Input value $ v $. This command adds $ v $ to all values in $ A_1～A_n $.

Snuke, having no other choice, decided to write a program to respond to these commands. However, he is having trouble, so he needs your help.

Note that Snuke will not execute the Set command after the initial one, and the input will only include commands other than the initial Set command.

Input Format

None

Output Format

Output the result of the $ i $th Command 2 on the $ i $th line.

Sample Input and Output

Sample Input #1

5 7
3 5
2 3
1 3 10
2 3
1 4 10
2 3
2 4

Sample Output #1

5
13
15
15

Sample Input #2

3 6
2 1
3 9
1 3 3
2 1
1 1 1
2 1

Sample Output #2

0
12
12

Notes/Hints

Scoring

There are no partial points for this problem.

Sample Explanation 1

The values of $ A_{i} $ change as follows: $ [A_{1},A_{2},A_{3},A_{4},A_{5}] $ : $ [0,0,0,0,0]→[5,5,5,5,5]→[13,13,13,5,5]→[15,15,15,15,5] $

Input Example 2

3 6
2 1
3 9
1 3 3
2 1
1 1 1
2 1

Output Example 2

0
12
12

见题面 Input 部分

见题面 Output 部分