P1038 The FLF Tokens

Problem Background

The NFLS (Nasty Fluffy Lost School) is holding the Foreign Language Festival (FLF). There’s a kind of tokens of this Festival, too! So Cui2010 and AppOfficer are willing to get it.

As AppOfficer is a student of the school, he again get them easily. Cui2010 was not happy at all! But he must play in a class’s show to get them! Unfortunately, he choose AppOfficer’s class (Class 10, Junior 1 (202110)). The class is going to put on a play. It’s topic is “What time is it?”. But AllenWither, The Life Committee of the class, also an OIer, says that Cui2010 has to answer an OI problem from him to join in.

Can you help Cui2010 answer the problem?

Problem Statement

As the Life Committee, AllenWither needs to manage the income and the outcome of the class’s money. On April 1, he got the bill of the \(n\) days before April 1: \(\left\{A_1,A_2,A_3,\cdots,A_n\right\}\) (\(A_i\) means the bill number of the \(i^{th}\) day in the \(n\) days). But, as it is April 1, the student who gave him the bill paper is trying to fool him. The bill paper is not accurate. AllenWither discovered this, and asked the student to make the bill paper correct.

The student gives AllenWither \(m\) queries, which includes these different operations:

• 1 x y means to modify the bill number on Day \(x\) to \(y\).
• 2 x means the student wants to know the current bill number on Day \(x\).
• 3 x y means the student wants to know the average bill number from Day \(x\) to Day \(y\) (floor the answer).
• 4 x y means the student wants to know the maximum bill number from Day \(x\) to Day \(y\).
• 5 x y means the student wants to know the minimum bill number from Day \(x\) to Day \(y\).
• 6 x y means the student wants to know the difference of the bill numbers of Day \(x\) and Day \(y\). (\(|A_x-A_y|\))
• 7 x y means the student wants to know the sum of the bill numbers of Day \(x\) to Day \(y\).
• 8 x y means the student wants to know the sum of the bill numbers of the first \(x\) days and the last \(y\) days.
• Notes: It is not a must that \(x\le y\) in the \(3^{rd}\) to the \(8^{th}\) operations.

As AllenWither is too busy caring about the class managements, he gives this problem to Cui2010.

So, solve this problem!

Input

\(n\ m\)
\(A_1\ A_2\ A_3\ \cdots\ A_n\)
\(\text{query}_{1}\)
\(\text{query}_2\)
\(\text{query}_3\)
\(\ \ \ \ \vdots\)
\(\text{query}_m\)

Output

For each query with the \(2^{nd}\) to the \(8^{th}\) operation, print the answer in lines.

Constraints

• All numbers in input are integers.
• \(1 \le n \le 5\times10^4\).
• \(1 \le m \le 10^5\).
• \(-2^{16} \le A_i < 2^{16}\).
• For queries:
  • The \(1^{st}\) query: \(1 \le x \le n\), \(-2^{16} \le y < 2^{16}\).
  • The \(2^{nd}\) query: \(1 \le x \le n\).
  • The \(3^{rd}\) to the \(8^{th}\) query: \(1 \le x \le n\), \(1 \le y \le n\).

Samples

Input 1

5 8
1 2 3 4 5
1 3 8
2 3
3 1 5
4 1 5
5 1 5
6 1 5
7 1 5
8 1 5

Output 1

8
4
8
1
4
20
21