1214: #6186. Attack

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

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

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

每次你有三种操作：

1. 攻击你左边的第一个没有被摧毁的巢穴，要求你的攻击力要大于等于它的防御力。

2. 攻击你右边的第一个没有被摧毁的巢穴，要求你的攻击力要大于等于它的防御力。

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

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

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

1. 交换巢穴 $x$ 和 $x+1$。

2. 给出两个数字 $x$ 和 $y$，求 ∑i=xyEi\sum_{i=x}^y E_i∑​i=x​y​​E​i​​ 的值。

输入格式

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

第二行 $n$ 个整数，表示 RiR_iR​i​​。

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

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

输出格式

对于每个 $\mathrm{o}\mathrm{p}=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\le 1000,q\le 2000$。

另外 $20\%$ 的分数满足没有操作 $1$。

另外 $30\%$ 的分数满足 RiR_iR​i​​ 两两不同。

$100\%$ 的分数满足 n≤105,k≤106,Ri≤109,q≤2×105,x<nn \leq 10^5, k \leq 10^6, R_i \leq 10^9, q \leq 2 \times 10^5, x < nn≤10​5​​,k≤10​6​​,R​i​​≤10​9​​,q≤2×10​5​​,x<n。