問題
長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $が与えられます。
$Q \ $個のクエリが与えられるので順に処理してください。$i \ $番目のクエリでは整数$ \ t_i,x_i,y_i \ $が与えられ、クエリの内容は以下の通りです。
- $t_i = 1 \ $のとき：$ \ a_{x_i} \ $を$ \ y_i \ $に更新する
- $t_i = 2 \ $のとき：$ \ a_{x_i}, a_{x_i + 1}, \ldots, a_{y_i} \ $の公約数の総和を出力する
入力
入力は以下の形式で標準入力から与えられる。
$N \ Q$ $a_1 \ a_2 \ \ldots \ a_N$ $t_1 \ x_1 \ y_1$ $t_2 \ x_2 \ y_2$ $\vdots$ $t_Q \ x_Q \ y_Q$
出力
$t_i = 2 \ $であるクエリに対する答えを順に改行区切りで出力せよ。
制約
- $1 \leq N,Q \leq 2 \times 10^5$
- $1 \leq a_i \leq 10^6$
- $t_i \in \{1,2\}$
-
$t_i = 1 \ $のとき
- $1 \leq x_i \leq N$
- $1 \leq y_i \leq 10^6$
-
$t_i = 2 \ $のとき
- $1 \leq x_i \leq y_i \leq N$
- 入力は全て整数
入出力例
入力例
5 5 2 2 4 6 9 1 3 3 2 3 5 1 2 8 2 1 3 2 5 5
出力例
4 1 13
- クエリ1:$ \ A = (2,2,3,6,9) \ $となる
- クエリ2:$ \ 3,6,9 \ $の公約数は$ \ 1,3 \ $なので和は$ \ 4 \ $となる
- クエリ3:$ \ A = (2,8,3,6,9) \ $となる
- クエリ4:$ \ 2,8,3 \ $の公約数は$ \ 1 \ $なので和は$ \ 1 \ $となる
- クエリ5:$ \ 9 \ $の約数は$ \ 1,3,9 \ $なので和は$ \ 13 \ $となる