E - Multiple Bonus Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N 人の社員を管理する部門長です。各社員には 1 から N までの社員番号が付けられており、社員 i の初期評価ポイントは S_i です。

社員 i の現在の評価ポイントを T_i とします。はじめ、T_i = S_i（1 \leq i \leq N）です。

この会社には独特の評価制度があります。ある社員 k（1 \leq k \leq N）がチームリーダーとして成果を上げると、社員番号が k の倍数（k, 2k, 3k, \ldots）であり N 以下であるすべての社員の評価ポイントに、成果に応じたボーナスポイントが加算されます。k 自身も k の倍数であるため、対象に含まれます。

高橋君はこの評価システムに対して Q 回の操作を行います。各操作は以下の 2 種類のいずれかです。

  • 操作 1：正の整数 k（1 \leq k \leq N）と正の整数 v が与えられる。社員番号が k の倍数であり N 以下であるすべての社員 j（すなわち j = k, 2k, 3k, \ldots かつ j \leq N）の評価ポイント T_j に v を加算する。
  • 操作 2：正の整数 x（1 \leq x \leq N）が与えられる。社員 1 から社員 x までの現在の評価ポイントの合計値 \displaystyle\sum_{i=1}^{x} T_i を出力する。

すべての操作 2 に対して、正しい答えを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq S_i \leq 10^9
  • 操作 1 において、1 \leq k \leq N
  • 操作 1 において、1 \leq v \leq 10^9
  • 操作 2 において、1 \leq x \leq N
  • 操作 2 は 1 回以上与えられる
  • 入力はすべて整数である
  • 出力すべき値は 2^{63} - 1 以下であることが保証される（符号付き 64 ビット整数に収まる）

入力

N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • 1 行目には、社員の数 N と操作の回数 Q がスペース区切りで与えられる。
  • 2 行目には、各社員の初期評価ポイント S_1, S_2, \ldots, S_N がスペース区切りで与えられる。
  • 続く Q 行にわたって、各操作が 1 行ずつ与えられる。
  • 操作 1 の場合：1 k v の形式で与えられる。
  • 操作 2 の場合：2 x の形式で与えられる。

出力

操作 2 が与えられるたびに、社員 1 から社員 x までの評価ポイントの合計値を 1 行に出力せよ。

入力例 1

5 6
1 2 3 4 5
2 3
1 2 10
2 5
1 1 1
2 1
2 4

出力例 1

6
35
2
34

入力例 2

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

出力例 2

19
6
27
10

入力例 3

12 10
3 1 4 1 5 9 2 6 5 3 5 8
2 6
1 3 4
2 12
1 5 7
2 10
1 2 1
1 12 100
2 12
2 1
2 11

出力例 3

23
68
65
188
3
75

入力例 4

20 14
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
2 20
1 4 25
1 6 10
2 12
1 1 3
2 5
1 10 100
2 20
1 7 8
1 20 50
2 19
2 20
1 3 6
2 18

出力例 4

2100
875
190
2515
2203
2581
2046

入力例 5

1 4
1000000000
2 1
1 1 1000000000
2 1
2 1

出力例 5

1000000000
2000000000
2000000000

Score : 466 pts

Problem Statement

Takahashi is a department manager who manages N employees. Each employee is assigned an employee number from 1 to N, and the initial evaluation points of employee i are S_i.

Let T_i denote the current evaluation points of employee i. Initially, T_i = S_i (1 \leq i \leq N).

This company has a unique evaluation system. When a certain employee k (1 \leq k \leq N) achieves results as a team leader, bonus points corresponding to the achievement are added to the evaluation points of all employees whose employee numbers are multiples of k (k, 2k, 3k, \ldots) and are at most N. Since k itself is a multiple of k, it is included in the targets.

Takahashi performs Q operations on this evaluation system. Each operation is one of the following two types:

  • Operation 1: Given a positive integer k (1 \leq k \leq N) and a positive integer v. Add v to the evaluation points T_j of all employees j whose employee numbers are multiples of k and are at most N (i.e., j = k, 2k, 3k, \ldots and j \leq N).
  • Operation 2: Given a positive integer x (1 \leq x \leq N). Output the sum of the current evaluation points from employee 1 to employee x: \displaystyle\sum_{i=1}^{x} T_i.

For all operations of type 2, output the correct answer.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq S_i \leq 10^9
  • In operation 1, 1 \leq k \leq N
  • In operation 1, 1 \leq v \leq 10^9
  • In operation 2, 1 \leq x \leq N
  • Operation 2 is given at least once
  • All input values are integers
  • It is guaranteed that the values to be output are at most 2^{63} - 1 (they fit in a signed 64-bit integer)

Input

N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • The first line contains the number of employees N and the number of operations Q, separated by a space.
  • The second line contains the initial evaluation points S_1, S_2, \ldots, S_N of each employee, separated by spaces.
  • The following Q lines each contain one operation.
  • For operation 1: given in the format 1 k v.
  • For operation 2: given in the format 2 x.

Output

Each time operation 2 is given, output the sum of evaluation points from employee 1 to employee x on one line.

Sample Input 1

5 6
1 2 3 4 5
2 3
1 2 10
2 5
1 1 1
2 1
2 4

Sample Output 1

6
35
2
34

Sample Input 2

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

Sample Output 2

19
6
27
10

Sample Input 3

12 10
3 1 4 1 5 9 2 6 5 3 5 8
2 6
1 3 4
2 12
1 5 7
2 10
1 2 1
1 12 100
2 12
2 1
2 11

Sample Output 3

23
68
65
188
3
75

Sample Input 4

20 14
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
2 20
1 4 25
1 6 10
2 12
1 1 3
2 5
1 10 100
2 20
1 7 8
1 20 50
2 19
2 20
1 3 6
2 18

Sample Output 4

2100
875
190
2515
2203
2581
2046

Sample Input 5

1 4
1000000000
2 1
1 1 1000000000
2 1
2 1

Sample Output 5

1000000000
2000000000
2000000000