『新的风暴已经出现，怎么能够停滞不前』—— 你决定去攻击小怪兽的巢穴。
怪兽有一行 nnn 个巢穴，从 111 到 nnn 编号，第 iii 个巢穴的防御力为 RiR_iRi。
一开始你在降生在第 xxx 个巢穴（此时巢穴 xxx 已被破坏），攻击力为 RxR_xRx。
每次你有三种操作：
攻击你左边的第一个没有被摧毁的巢穴，要求你的攻击力要大于等于它的防御力。
攻击你右边的第一个没有被摧毁的巢穴，要求你的攻击力要大于等于它的防御力。
增加你的攻击力，这会占用你 kkk 次操作，你的攻击力会变成两边第一个没有被摧毁的巢穴防御力的较小值（不存在算作 ∞\infty∞）。
令 ExE_xEx 等于你出生在 xxx 的时候，捣毁所有巢穴需要的最少次数。
现在有 qqq 个操作，每次为以下两种之一：
交换巢穴 xxx 和 x+1x + 1x+1。
给出两个数字 xxx 和 yyy，求 ∑i=xyEi\sum_{i=x}^y E_i∑i=xyEi 的值。
第一行两个整数 nnn 和 kkk。
第二行 nnn 个整数，表示 RiR_iRi。
之后若干行（qqq 行，直至文件末尾），开始一个数 op\mathrm{op}op 表示操作类型。
对于每个 op=2\mathrm{op} = 2op=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%20\%20% 的分数满足 n≤1000,q≤2000n \leq 1000, q \leq 2000n≤1000,q≤2000。
另外 20%20\%20% 的分数满足没有操作 111。
另外 30%30\%30% 的分数满足 RiR_iRi 两两不同。
100%100\%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≤105,k≤106,Ri≤109,q≤2×105,x<n。