Problem Description

In the Paken Kingdom, there are $ N $ schools numbered $1, 2, \ldots, N$. Initially, school $ i $ has $ A_i $ students. Of course, since they are schools, the same people cannot remain in the school forever. The number of students may change over time.

The Paken Kingdom hosts competitions almost every day, and for each competition, an integer pair $ (l, r) $ representing the candidate schools to invite is determined. From schools $l, l+1, \ldots, r$, only one school is selected, and all students from that school are invited.

For the competitions, snacks are distributed to participants for sugar intake. However, the number of snacks has the following conditions:

• To ensure that the number of snacks does not vary among people, for any school in $l, l+1, \ldots, r$, the number of students in that school must be a divisor of the number of snacks prepared.
• The Paken Kingdom does not have much money, so the number of snacks prepared should be the smallest possible that satisfies the above condition.

You are the CEO of the only snack company in the Paken Kingdom. All snacks for the competitions are ordered from your company. You want to know which schools are candidates for being invited to the competitions for the sake of your company's PR. Therefore, for each competition, you decided to calculate the number of possible integer pairs $ (l, r) $ from the number of snacks ordered.

There are $ Q $ events in the Paken Kingdom, each represented by one of the following types of queries:

• Enrollment query 1 k a: $ a $ students enroll in school $ k $. The number of students in school $ k $ increases by $ a $.
• Graduation query 2 k b: $ b $ students graduate from school $ k $. The number of students in school $ k $ decreases by $ b $.
• Competition query 3 s: A competition orders $ s $ snacks. You need to calculate the number of possible integer pairs $ (l, r) $ for the competition.

When $ Q $ events occur sequentially, find the answer for each competition query.

Note that since schools are schools, the number of students in any school is always guaranteed to be between $ 1 $ and $ 10^9 $ at any time.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_1 $ $ A_2 $ $\ldots$ $ A_N $ $\mathrm{query}1$ $\mathrm{query}2$ $\vdots$ $\mathrm{query}Q$

For the $ i $th query $\mathrm{query}i$, an integer $ c_i $ ($ 1, 2, or 3 $) representing the type of query is given first.

If $ c_i = 1 $, two more integers $ k $ and $ a $ are given.

If $ c_i = 2 $, two more integers $ k $ and $ b $ are given.

If $ c_i = 3 $, one more integer $ s $ is given.

Thus, each query is in one of the following formats:

$ 1 $ $ k $ $ a $

$ 2 $ $ k $ $ b $

$ 3 $ $ s $

Output Format

Let $ q $ be the number of queries satisfying $ c_i = 3 $. Output $ q $ lines, where the $ j $th line ($1 \leq j \leq q$) contains the answer for the $ j $th such query.

Sample Input and Output

Sample Input #1

4 3
1 2 3 4
3 12
1 1 3
3 12

Sample Output #1

3
4

Sample Input #2

10 5
10 1 8 3 10 10 6 3 3 7
3 30
3 7
3 4
3 10
3 1

Sample Output #2

11
1
0
5
1

Sample Input #3

20 20
13 5 30 10 15 22 30 4 11 18 10 23 9 1 27 8 5 6 16 26
3 60
3 90
2 19 11
2 7 6
2 5 6
3 12870
3 198
1 12 3
2 10 1
3 30
3 5
2 18 5
3 234
3 291720
1 10 6
3 1776060
3 198
3 10
3 792
3 30

Sample Output #3

1
1
1
2
7
3
2
2
1
1
2
3
4

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_j \leq 10^9$ ($1 \leq j \leq N$)
• For enrollment and graduation queries, $1 \leq k \leq N$
• For enrollment queries, $1 \leq a \leq 10^9$
• For graduation queries, $1 \leq b \leq 10^9$
• For competition queries, $1 \leq s \leq 10^9$
• At any point, the number of students in any school is between $ 1 $ and $ 10^9 $
• All inputs are integers

Subtasks

1. ($ 150 $ points) $N, Q \leq 10^3$
2. ($ 200 $ points) No enrollment or graduation queries are given
3. ($ 200 $ points) At any point, the number of students in any school is $ 10 $ or less
4. ($ 150 $ points) No additional constraints

Sample Explanation 1

The results of each query are as follows:
1. Competition query. $ (l, r) = (1, 4), (2, 4), (3, 4) $ satisfy the condition.
2. Enrollment query. $ 3 $ students enroll in school $ 1 $, making the number of students $ 4, 2, 3, 4 $ respectively.
3. Competition query. $ (l, r) = (1, 3), (1, 4), (2, 4), (3, 4) $ satisfy the condition. This input example satisfies the constraints of subtasks $ 1, 3, 4 $.

Sample Explanation 2

This input example satisfies the constraints of all subtasks.

Sample Explanation 3

This input example satisfies the constraints of subtasks $ 1, 4 $. Original idea: [MATH0]

见题面 Input 部分

见题面 Output 部分