# [Usaco2015 dec]Counting Haybales

### 题目描述

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has made the project perhaps more complicated than necessary. Please help him follow his instructions to complete the farm upgrade.

FJ's farm consists of NN fields in a row, conveniently numbered 1…N1…N. In each field there can be any number of haybales. Farmer John's instructions contain three types of entries:

1) Given a contiguous interval of fields, add a new haybale to each field.

2) Given a contiguous interval of fields, determine the minimum number of haybales in a field within that interval.

3) Given a contiguous interval of fields, count the total number of haybales inside that interval.

1) 对一个连续区间的土地，每块土地增加相同数量的草堆。
2) 对一个连续区间的土地，输出其中最少的草堆数量。
3) 对一个连续区间的土地，输出草堆数量总数。

### 输入格式

The first line contains two positive integers, N (1≤N≤200,000) and Q (1≤Q≤100,000).

The next line contains N nonnegative integers, each at most 100,000, indicating how many haybales are initially in each field.

Each of the next Q lines contains a single uppercase letter, either M, P or S, followed by either two positive integers AA and BB (1≤A≤B≤N), or three positive integers AA, BB, and CC (1≤A≤B≤N; 1≤C≤100,000). There will be three positive integers if and only if the uppercase letter is P.

If the letter is M, print the minimum number of haybales in the interval of fields from A…B.

If the letter is P, put C new haybales in each field in the interval of fields from A…B.

If the letter is S, print the total number of haybales found within interval of fields from A…B.

### 输出格式

A line in the output should appear in response to every 'M' or 'S' entry in FJ's instructions.

```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```

### 题目来源

Platinum鸣谢Claris提供译文