JOI 制药公司（IOI Pharmaceutical Co., Ltd.）的 JOI 先生正在忙于开发新型杀菌喷雾的实验工作。

在该公司中，杀菌喷雾的强度定义如下：当我们对一个含有 $y$ 个细菌的培养皿使用一次强度为 $x$ 的喷雾时，该培养皿上的细菌数量变为 $\lfloor y/x \rfloor$，即 $y/x$ 向下取整得到的整数。现在，公司开发出了一种强度为 $K$ 的新喷雾。为了测试这种喷雾的性能，他们计划进行一项实验。他们使用了编号为 $1, \dots, N$ 的 $N$ 个培养皿。实验开始时，培养皿 $i$ 上有 $C_i$ 个细菌。在实验中，他们按顺序执行 $Q$ 次操作。每次操作为以下三种之一：

• 操作 1：选择一个培养皿 $a$ 和一个整数 $b$，调整培养皿 $a$ 上的细菌数量。执行此操作后，培养皿 $a$ 上的细菌数量变为 $b$。
• 操作 2：选择两个整数 $l, r$，满足 $1 \le l \le r \le N$。对培养皿 $l, l + 1, \dots, r - 1, r$ 各喷洒一次喷雾。
• 操作 3：选择两个整数 $l, r$，满足 $1 \le l \le r \le N$。计算培养皿 $l, l + 1, \dots, r - 1, r$ 上的细菌数量之和，并记录下来。

JOI 先生对假设新喷雾按预期工作后的实验结果感到好奇。由于你是一名优秀的程序员，他请求你预测实验的结果。

编写一个程序，确定实验中操作 3 所记录的数值。

输入格式

从标准输入读取以下数据：

• 第一行包含三个空格分隔的整数 $N, Q, K$。这表示喷雾的强度为 $K$，培养皿的数量为 $N$，实验中的操作次数为 $Q$。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $C_i$。这表示实验开始时培养皿 $i$ 上的细菌数量为 $C_i$。
• 接下来的 $Q$ 行中，第 $i$ 行（$1 \le i \le 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 所记录的数值。输出的行数应等于实验中执行操作 3 的次数。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le K \le 10$
• $0 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$)
• $1 \le S_i \le 3$ ($1 \le i \le Q$)
• 当 $S_i = 1$ 时，$1 \le T_i \le N$ 且 $0 \le U_i \le 1\,000\,000\,000$ ($1 \le i \le Q$)
• 当 $S_i = 2, 3$ 时，$1 \le T_i \le U_i \le N$ ($1 \le i \le Q$)

子任务

子任务 1 [5 分]

• $1 \le N \le 3\,000$
• $1 \le Q \le 3\,000$

子任务 2 [10 分]

• $C_i \le 1$ ($1 \le i \le N$)
• 当 $S_i = 1$ 时，$U_i \le 1$ ($1 \le i \le Q$)

子任务 3 [10 分]

• $K = 1$

子任务 4 [75 分]

• 无附加限制。

样例

样例输入 1

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

样例输出 1

8
3
8

样例输入 2

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

样例输出 2

174
444
76
23
41