小千是一位喜欢在游戏 中制作像素画的玩家。一天，她梦见自己进入了一个 的 世界，其中只有 坐标和 坐标（ 坐标表示高度，且 ）。梦境中的世界杂乱无章，分布着许多方块，但所有方块都位于整数坐标上。

为了整理这片区域，小千计划对 坐标在 范围内的方块进行一系列操作。由于梦中的她不能自如的使用飞行功能，这使得她认为每个方块的破坏难度取决于其高度：高度为 的方块的破坏难度为 。因此，高度越低的方块，破坏难度越小。初始时，小千会告诉你每个 坐标上所有方块的破坏难度之和。

接下来，小千会进行 次操作，每次操作是以下两种类型之一：

. 清除操作：给定区间 （），小千会清除该区间内所有破坏难度最小的方块。

. 查询操作：给定区间 ，计算该区间内所有方块的破坏难度之和。

梦中的她思绪混乱，需要在你的辅助下才能完成这些工作。你的任务是正确处理这些操作，并输出每次询问的结果，以帮助小千高效地完成清理工作。

第一行包含两个整数  和 （），分别表示整个区域宽度和操作次数。

第二行包含  个整数，第  个整数表示初始时  位置上所有方块的破坏难度之和 （）。

接下来  行，每行包含三个整数表示一个操作，具体如下：

- `1 l r` 表示清除 （）范围内所有破坏难度最小的方块。
- `2 l r` 表示输出 （）范围内所有方块的破坏难度之和。

对于每个询问操作，输出一行一个整数，表示询问的结果。

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

15
12
8