题目描述

在育华学校的劳动节期间，图书馆异常热闹，同学们纷纷前来借阅图书。图书馆有 $n$ 个书架（$1 \leq n \leq 10^5$），每个书架初始有 $a_i$ 本图书（$1 \leq a_i \leq 10^3$）。

学校为了更好地管理图书借阅情况，需要进行两种操作：

1. 借阅操作：给定区间 $[l, r]$ 和数量 $x$，表示从书架 $l$ 到书架 $r$ 每个书架借出 $x$ 本图书（$1 \leq x \leq 100$）。如果某个书架的图书数量不足 $x$ 本，则该书架的图书全部被借出。
2. 查询操作：给定区间 $[l, r]$，查询书架 $l$ 到书架 $r$ 剩余图书的总数。

请你编写一个程序，处理这些操作并输出每次查询操作的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq m \leq 10^5$），分别表示书架的数量和操作的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每个书架初始的图书数量。 接下来 $m$ 行，每行表示一个操作：

• 若为借阅操作，格式为 1 l r x。
• 若为查询操作，格式为 2 l r。

输出格式

对于每个查询操作，输出一行一个整数，表示该区间内剩余图书的总数。

样例

• 输入

5 5
10 20 30 40 50
1 2 4 5
2 1 5
1 3 5 20
2 2 4
2 1 1

• 输出

135
35
10