题目描述

$\red{Farmer John }$正试图聘请承包商来帮助重新布置他的农场，但到目前为止，当他们看到 $\red{FJ }$希望他们遵循的复杂指令序列时，所有人都退出了。他独自完成了这个项目，他意识到确实，他让这个项 目可能比必要的复杂得多。请帮助他按照他的指示完成农场升级。

$\red{FJ }$的农场包括?连续的字段，方便编号$\red{1… }$ $\red{N. }$在每个领域都可以有任意数量的干草捆。$\red{Farmer John }$的说明包含三种类型的条目：

$\red{1）}$给定一个连续的字段间隔，为每个字段添加一个新的干草。

$\red{2) }$给定一个连续的田地间隔，确定该间隔内田地中干草的最小数量。

$\red{3）}$给定一个连续的字段区间，计算该区间内的干草堆总数。

输入格式

第一行包含两个正整数，$\red{N（}$$\red{1≤}$$\red{N≤}$$\red{200000）}$和$\red{Q（}$$\red{1≤}$$\red{Q≤}$$\red{100,000)}$。

下一行包含$\red{N}$个非负整数，每个非负整数最多为$\red{100000，}$表示每个字段中最初有多少草包。

接下来的每一个$\red{Q}$行都包含一个大写字母，$\red{M}$、$\red{P}$或$\red{S，}$后跟两个正整数$\red{a}$和$\red{B（}$$\red{1≤}$$\red{A.≤}$$\red{B≤}$$\red{N）}$ ，或三个正整数$\red{A}$、$\red{B}$和$\red{C（}$$\red{1≤}$$\red{A.≤}$$\red{B≤}$$\red{N，1≤}$$\red{C≤}$$\red{100,000). }$当且仅当大写字母为$\red{P}$时，将有三个正整数。

如果字母为$\red{M，}$则从$\red{A…}$$\red{B}$打印字段间隔中的最小草包数。

如果字母是$\red{P，}$则在$\red{A…}$$\red{B}$的田地间隔中，在每个田地中放置$\red{C}$个新草包。

如果字母是$\red{S，}$则打印在$\red{A…}$$\red{B}$的字段间隔内找到的草包总数。

输出格式

输出中应出现一行以响应 $\red{FJ }$指令中的每个"$\red{M}$"或"$\red{S}$"条目。

样例

输入样例

4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 3

输出样例

2
6
3
8