《鱿鱼游戏》的新一季即将开始！负责人（Frontman）让你负责本季的第三个游戏——Mingle。

Mingle 游戏由初始玩家人数 $p$、安全屋数量 $m$ 以及一个由 $k$ 个正整数组成的序列 $b_1, \dots, b_k$ 决定。

游戏共进行 $k$ 轮。在第 $i$ 轮中，剩余的玩家需要组成人数恰好为 $b_i$ 的队伍，且每支队伍必须躲进 $m$ 个安全屋中的一个。每个安全屋最多容纳一支队伍。如果玩家没有加入人数为 $b_i$ 的队伍，或者他们的队伍没有躲进安全屋，他们就会被淘汰。

所有在第 $i$ 轮中幸存的玩家将晋级到下一轮（第 $i+1$ 轮）。队伍在轮与轮之间可以任意重新组合。成功通过第 $k$ 轮的玩家将被宣布为 Mingle 游戏的获胜者。

负责人对计算游戏中可能的最大获胜者人数很感兴趣。然而，由于初始玩家人数和序列本身都尚未确定，你需要回答关于该游戏的多个查询。

在开始时，给你一个大小为 $n$ 的序列 $a$ 和安全屋数量 $m$，它们在所有查询中都是固定的。接下来有 $q$ 个查询。每个查询是以下两种类型之一：

• $1\ i\ x$（$1 \le i \le n, 1 \le x \le 10^9$）— 将 $a_i$ 更新为 $x$（即 $a_i := x$）。
• $2\ l\ r\ p$（$1 \le l \le r \le n, 1 \le p \le 10^9$）— 如果在序列 $a_l, a_{l+1}, \dots, a_r$ 上进行以 $m$ 个安全屋和 $p$ 名初始玩家为参数的 Mingle 游戏，最大获胜者人数是多少？

对于每个类型 2 的查询，输出可能的最大获胜者人数。请注意，类型 2 的查询之间是相互独立的。

输入格式

第一行包含两个整数 $n, m$（$1 \le n \le 2 \cdot 10^5, 1 \le m \le 100$）— 序列 $a$ 的大小和安全屋的数量。

第二行包含 $n$ 个空格分隔的整数 $a_1, \dots, a_n$（$1 \le a_i \le 10^9$）— 初始序列。

第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）— 查询的数量。

接下来的 $q$ 行描述查询，每行一个，格式如上所述。

输出格式

按输入中出现的顺序，每行输出一个类型 2 查询的答案。

样例

输入样例 1

5 50
10 4 3 6 2
5
2 1 5 255
1 3 13
2 1 4 456
1 5 7
2 3 5 150

输出样例 1

100
192
133

输入样例 2

6 30
18 55 19 30 87 10
6
2 2 4 540
1 4 41
2 1 6 350
1 1 49
2 1 5 666
2 3 6 210

输出样例 2

480
260
522
170

输入样例 3

3 100
40 50 60
4
2 1 3 4000
1 1 30
1 3 45
2 1 3 4000

输出样例 3

3960
2970

说明

在第一个测试样例的第一个查询中，由于安全屋数量有限，在第 5 轮中最多只能有 100 名玩家幸存。

在第一个测试样例的第三个查询中，在第 2 轮中最多只能有 200 名玩家幸存。接着，在第 3 轮中，这 200 名玩家最多可以组成 15 支人数为 13 的队伍，剩下 5 名玩家。在第 4 轮中，剩余的 195 名玩家最多可以组成 32 支人数为 6 的队伍，最终产生 192 名获胜者。