AT_pakencamp_2021_day3_e お菓子
题目描述
# 点心
Paken 王国有 $N$ 所学校，校园编号从 $1$ 到 $N$。初始情况下，第 $i$ 所学校有 $A_i$ 名学生。由于是学校，同一人不能永远在同一所学校就读。学生人数可能会发生变化。
Paken 王国经常举办王国举办的比赛，每次比赛都会确定一组候选学校，该组学校由整数对 $(l, r)$ 表示，表示从学校 $l$ 到学校 $r$ 中选择一所学校，然后邀请该学校的所有学生参加比赛。
比赛是脑力比赛，为了供应糖分，参赛者会获得点心。然而，点心的数量有以下条件：
- 为了保证每个学校的学生获得的点心数量一样，学校 $l,\ l+1,\ \ldots,\ r$ 中的任意一所学校的学生人数应该是点心数量的约数。
- Paken 王国财政紧张，所以在满足上述条件的情况下，糖果的数量应该尽量少。
你是 Paken 王国唯一的点心公司的总裁。所有比赛的糖果都会向你的公司订购。为了公司的公关，你想知道哪些学校是比赛的候选学校。因此，你决定统计每次比赛订购的点心数量，以及满足给定整数 $s$ 的约束条件 $(l,r)$ 可能的数量。
Paken 王国将发生 $Q$ 个事件，每个事件用以下查询之一表示：
- 入学查询 `1 k a` ：学校 $k$ 有 $a$ 名学生入学。学校 $k$ 的学生人数增加 $a$ 人。
- 毕业查询 `2 k b` ：学校 $k$ 有 $b$ 名学生毕业。学校 $k$ 的学生人数减少 $b$ 人。
- 比赛查询 `3 s` ：某次比赛订购了 $s$ 颗点心。你需要计算满足条件的约数对 $(l,r)$ 的可能数量。
给定 $Q$ 个事件按顺序发生，对于每个比赛查询，你需要计算答案。
需要注意的是，学校毕竟是学校，所以在任何时候，每所学校的学生人数都保证在 $1$ 到 $10^9$ 之间。
输入格式
输入从标准输入读取，格式如下：
> $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}1 $ $ \mathrm{query}2 $ $ \vdots $ $ \mathrm{query}Q $
第 $i$ 个查询 $Query_i$ 由以下形式之一表示：
- 每个插入查询包含三个整数：$c_i, k, a$，其中 $c_i$ 是查询的类型（$1, 2, 3$ 中的一个），$k$ 是学校编号，$a$ 是学生人数。
- 每个比赛查询包含两个整数：$c_i, s$，其中 $c_i$ 是查询的类型（$1, 2, 3$ 中的一个），$s$ 是订购的糖果数量。
换句话说，每个查询可以是以下三种形式之一：
> $1$ $k$ $a$
> $2$ $k$ $b$
> $3$ $s$
输出格式
输出结果到标准输出，格式如下：
对于每个比赛查询，输出 $q$ 行。第 $j$ 行（$1 ≤ j ≤ q$）输出对于第 $j$ 个查询的答案。
## 样例 #1
### 样例输入 #1
```
4 3
1 2 3 4
3 12
1 1 3
3 12
```
### 样例输出 #1
```
3
4
```
## 样例 #2
### 样例输入 #2
```
10 5
10 1 8 3 10 10 6 3 3 7
3 30
3 7
3 4
3 10
3 1
```
### 样例输出 #2
```
11
1
0
5
1
```
## 样例 #3
### 样例输入 #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
```
### 样例输出 #3
```
1
1
1
2
7
3
2
2
1
1
2
3
4
```
说明/提示
### 限制
- $1 ≤ N, Q ≤ 10^5$
- $1 ≤ A_j ≤ 10^9$，其中 $1 ≤ j ≤ N$
- 对于入学查询和毕业查询，$1 ≤ k ≤ N$
- 对于入学查询，$1 ≤ a ≤ 10^9$
- 对于毕业查询，$1 ≤ b ≤ 10^9$
- 对于比赛查询，$1 ≤ s ≤ 10^9$
- 在任何时候，保证对于每所学校，其学生人数在 $1$ 到 $10^9$ 之间
- 所有输入都是整数
### 子任务
1. ($150$ 分) $N, Q ≤ 10^3$
2. ($200$ 分) 不包含入学查询和毕业查询
3. ($200$ 分) 在任何时候，保证每所学校的学生人数不超过 $10$ 人
4. ($150$ 分) 没有额外的限制
### 样例解释 1
每个查询的结果如下： 1. 比赛查询。满足条件的 $(l,r)$ 是 $(1,4), (2,4), (3,4)$。 2. 入学查询。学校 $1$ 入学 $3$ 名学生，各个学校的学生人数变为 $4, 2, 3, 4$。 3. 比赛查询。满足条件的 $(l,r)$ 是 $(1,3), (1,4), (2,4), (3,4)$。该样例满足小任务 $1, 3, 4$ 的限制。
### 样例解释 2
该样例满足所有子任务的限制。
### 样例解释 3
该样例满足小任务 $1, 4$ 的限制。 原题: \[shiomusubi496\](https://atcoder.jp/users/shiomusubi496)