题目描述

『新的风暴已经出现，怎么能够停滞不前』—— 你决定去攻击小怪兽的巢穴。

怪兽有一行 $n$ 个巢穴，从 $1$ 到 $n$ 编号，第 $i$ 个巢穴的防御力为 $R_i$。

一开始你在降生在第 $x$ 个巢穴（此时巢穴 $x$ 已被破坏），攻击力为 $R_x$。

每次你有三种操作：

1. 攻击你左边的第一个没有被摧毁的巢穴，要求你的攻击力要大于等于它的防御力。
2. 攻击你右边的第一个没有被摧毁的巢穴，要求你的攻击力要大于等于它的防御力。
3. 增加你的攻击力，这会占用你 $k$ 次操作，你的攻击力会变成两边第一个没有被摧毁的巢穴防御力的较小值（不存在算作 $\infty$）。

令 $E_x$ 等于你出生在 $x$ 的时候，捣毁所有巢穴需要的最少次数。

现在有 $q$ 个操作，每次为以下两种之一：

• 交换巢穴 $x$ 和 $x + 1$。
• 给出两个数字 $x$ 和 $y$，求 $\sum_{i=x}^y E_i$ 的值。

输入格式

第一行两个整数 $n$ 和 $k$。

第二行 $n$ 个整数，表示 $R_i$。

之后若干行（$q$ 行，直至文件末尾），开始一个数 $\mathrm{op}$ 表示操作类型。

如果 $\mathrm{op} = 1$，接下来一个数 $x$。
否则 $\mathrm{op} = 2$，接下来两个数字 $x$ 和 $y$。参数含义均与题目描述中相同。

输出格式

对于每个 $\mathrm{op} = 2$ 的操作输出一行，包含一个整数表示答案。

样例

输入

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

输出

7
38
13
41

数据范围与提示

• $20\%$ 的分数满足 $n \leq 1000, q \leq 2000$。
• 另外 $20\%$ 的分数满足没有操作 1。
• 另外 $30\%$ 的分数满足 $R_i$ 两两不同。
• $100\%$ 的分数满足 $n \leq 10^5, k \leq 10^6, R_i \leq 10^9, q \leq 2 \times 10^5, x < n$。