题目描述

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

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

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

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

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

输入格式

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

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

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

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

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

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

输出格式

输出中应出现一行以响应 ${FJ }$指令中的每个"${M}$"或"${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