题目描述

译自 JOI Open 2015 T3 「殺菌スプレー / Sterilizing Spray」

JOI 先生在 IOI 制药有限公司工作。在这家公司，研究人员忙于开发新的杀菌喷雾。

在这家公司，杀菌喷雾的强度定义如下：当我们对一个有 $y$ 个细菌的培养皿使用一次强度为 $x$ 的喷雾时，培养皿上的细菌数变为 $\lfloor \frac{y}{x} \rfloor$。现在，IOI 制药开发出了一种强度为 $K$ 的新喷雾。为了测试这种喷雾的性能，他们计划对它进行实验。他们使用编号为 $1$ 到 $N$ 的 $N$ 个培养皿。在实验开始时，培养皿 $i$ 上有 $C_{i}$ 个细菌。在实验中，他们按顺序执行 $Q$ 个操作。每个操作是以下之一：

• 操作 1：选择一个培养皿 $a$ 和一个整数 $b$，并将培养皿 $a$ 上的细菌数改为 $b$。
• 操作 2：选择两个整数 $l, r\ (1 \leq l \leq r \leq N)$。对培养皿 $l, l+1, \ldots, r-1, r$ 各喷一次杀菌喷雾。
• 操作 3：选择两个整数 $l, r\ (1 \leq l \leq r \leq N)$。计算培养皿 $l, l+1, \ldots, r-1, r$ 上的细菌数之和，并记录下来。

JOI 先生对喷雾如果按照预期发挥作用的结果很好奇。由于你是一名优秀的程序员，他请你预测实验的结果。

给定喷雾的强度和实验中的操作信息，写一个程序对于每个操作 3，求出它记录的数字。

输入格式

第一行包含三个用空格分隔的整数 $N, Q, K$，表示喷雾的强度是 $K$，培养皿的数量是 $N$，实验中的操作数量是 $Q$。

接下来的 $N$ 行中的第 $i\ (1 \leq i \leq N)$ 行包含一个整数 $C_{i}$，表示在实验开始时培养皿 $i$ 上有 $C_{i}$ 个细菌。

接下来的 $Q$ 行中的第 $i\ (1 \leq i \leq Q)$ 行包含三个用空格分隔的整数 $S_{i}, T_{i}, U_{i}$，表示实验中第 $i$ 个操作的信息：

• 当 $S_{i}=1$ 时，它们表示操作 1，其中 $a=T_{i}, b=U_{i}$。
• 当 $S_{i}=2$ 时，它们表示操作 2，其中 $l=T_{i}, r=U_{i}$。
• 当 $S_{i}=3$ 时，它们表示操作 3，其中 $l=T_{i}, r=U_{i}$。

输出格式

对于每个操作 3，输出一行一个整数表示它记录的数字。

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

8
3
8

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

174
444
76
23
41

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq K \leq 10$
• $0 \leq C_{i} \leq 10^9\ (1 \leq i \leq N)$
• $1 \leq S_{i} \leq 3\ (1 \leq i \leq Q)$
• 当 $S_{i}=1$ 时，有 $1 \leq T_{i} \leq N$ 和 $0 \leq U_{i} \leq 10^9\ (1 \leq i \leq Q)$
• 当 $S_{i}=2,3$ 时，有 $1 \leq T_{i} \leq U_{i} \leq N\ (1 \leq i \leq Q)$

详细子任务附加限制及分值如下表所示。