大样例下载

题目背景

dzc 喜欢充足的氧气 QwQ（enougH oXYgen）。

题目描述

dzc 是一些电子厂的厂长，他手下有 $N$ 个电子厂，从 $1$ 到 $n$ 编号，排列在一条道路上。他们一直在生产氧气。一开始，第 $i$ 个工厂每天能产生 $a_i$ 单位的氧气。

现在他想要实现 $Q$ 个命令。

dzc 很喜欢充足的氧气，但是众所周知的是，吸纯氧会去世，对此他非常担忧。他有时会认为自己吸了超过 $p$ 单位的氧气会去世，所以他会下令把一个区间 $[l,r]$ 内的电子厂的氧气生产量全部取模 $p$。

而 dzc 也会害怕自己吸不到充足的氧气，而下令把 $pos$ 位置的氧气生产量改为 $x$。

dzc 经常需要去视察电子厂。在一次视察中，他会从第 $l$ 个工厂一直走到第 $r$ 个工厂。一次视察的满意度定义为这个区间里的电子厂的氧气生产量之和。dzc 很想知道在一次视察中他能得到的满意度，因为这样他就不用自己去了。

不幸的是，dzc 的 $998244353$ 个员工全都跑路了，他只好请你来帮他实施这些操作。

输入格式

第一行输入三个整数 $T,N,Q$，表示测试点编号,电子厂个数，操作个数。$T = 0$ 代表该测试点为样例。

接下来一行 $N$ 个整数，第 $i$ 个整数代表 $a_i$。

接下来有 $Q$ 行输入：

对于每一行，输入一个整数 $op$，代表操作类型。

若 $op = 1$，接下来输入两个整数 $pos,x$，表示将第 $pos$ 个电子厂的氧气生产量改为 $x$。

若 $op = 2$，接下来输入三个整数 $l,r,p$，表示将区间 $[l,r]$ 内的电子厂的氧气生产量取模 $p$。

若 $op = 3$，接下来输入两个整数 $l,r$，表示 dzc 视察区间 $[l,r]$ 后能得到的满意度。

输出格式

对于每一个 $op = 3$，输出一个整数，代表 dzc 能得到的满意度。

自测样例

pretest1

input

0 5 5
1 2 3 4 5
2 3 5 4
1 3 5
3 2 5
2 1 3 3
3 1 3

output

8
5

pretest2 见下发大样例。

数据范围

测试点编号	$N \leq$	$Q \leq$	特殊性质
$1 \sim 4$	$10^3$	$5 \times 10^3$	无
$5 \sim 6$	$10^5$	$10^5$	A
$7 \sim 8$			B
$9$			C
$10$		$10^6$
$11 \sim 20$			无

为防止卡评测，各部分分采用捆绑测试。

特殊性质A：不存在 $op = 2$。

特殊性质B：保证 $op = 2$ 的数量不大于 $50$。

特殊性质C：保证 $op = 3$ 操作的 $l = r$，且 $op = 3$ 时不同的 $l$ 不超过 $100$ 个，且 $op = 2$ 的操作随机生成。

对于所有数据，满足 $n \leq 10^5, Q \leq 10^6,1 \leq l \leq r \leq n,1 \leq x,a_i,p \leq 10^{12},1 \leq pos \leq n$。

保证非 $op = 2$ 的操作总和不超过 $10^5$。

本题输入数据量较大，请使用较快的输入方式。