Farm Upgrade

Farmer John's farm consists of \(N\) fields, numbered from 1 to \(N\). Initially, all fields contain 0 haybales. He has issued \(Q\) instructions that are one of the following types:

• 1 a b: For every field from \(a\) to \(b\) (inclusive), add one haybale.
• 2 a b: Report the minimum number of haybales among the fields from \(a\) to \(b\) (inclusive).
• 3 a b: Report the total number of haybales among the fields from \(a\) to \(b\) (inclusive).

Your task is to process these instructions efficiently. For every query of type 2 or 3, output the corresponding answer on a new line.

Note: Use lazy propagation with a segment tree to handle range updates and queries. The update operation increases both the sum and the minimum appropriately. For a segment covering \(L\) fields and an addition of \(v\), the sum increases by \(v \times L\) and the minimum by \(v\).

inputFormat

The first line contains two integers \(N\) and \(Q\) (e.g. \(1 \leq N, Q \leq 10^5\)).

Each of the following \(Q\) lines contains an instruction in the form:

type a b

• When type = 1: Add a haybale to each field from a to b (inclusive).
• When type = 2: Output the minimum number of haybales in fields a to b (inclusive).
• When type = 3: Output the sum of haybales in fields a to b (inclusive).

It is guaranteed that \(1 \le a \le b \le N\).

outputFormat

For each query of type 2 and type 3, output the answer on a separate line in the order they appear.

sample

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

3
0
1