406074: GYM102254 G Grade Concept

The semester is ending and Naum decides to establish the grade concept of the IME++ members. The concept is formed by several grades given by him to the members in moments of pride or disappointment during the semester, which can be represented as a sequence of grades, numbered from $$$1$$$ to $$$n$$$.

The grade concept could be just the sum of all the grades given by him, but Naum decided to complicate a little bit, creating the following criteria: the grade concept will be the sum of the grades from range $$$l$$$ to $$$r$$$, minus the value of the minimum and maximum value in this range (for normalization, of course). More formally, $$$f = sum(l, r) - max(l, r) - min(l, r)$$$, where $$$f$$$ is the grade concept, $$$sum(l, r)$$$, $$$max(l, r)$$$ and $$$min(l, r)$$$ is the sum of all grades, maximum grade and minimum grade, from $$$l$$$ to $$$r$$$, inclusive.

Besides that, Naum decides to change the grades of some members, because he thought members like Navarro deserved a better grade concept, while others like de Castro deserved a worst grade concept.

Naum is too busy trying to fix bugs from Bing and he asks you to create a program that can help him calculate the grade concept. He will give you a sequence of $$$n$$$ grades and $$$q$$$ queries of two types:

• $$$1$$$ $$$l$$$ $$$r$$$: answer the grade concept from $$$l$$$ to $$$r$$$.
• $$$2$$$ $$$i$$$ $$$v$$$: change the value of the $$$i$$$-th grade to $$$v$$$.

The first line contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the number of grades and the number of queries, respectively.

The next line contains $$$n$$$ space-separated integers, $$$grade_i$$$ ($$$0 \le grade_i \le 10$$$) — the value of the $$$i$$$-th grade.

The next $$$q$$$ lines contains, each, one integer, $$$t$$$ ($$$1 \le t \le 2$$$), indicating the type of the $$$i$$$-th query, and two other integers, described below, depending on the query type.

If $$$t_i$$$ equals $$$1$$$, the integers are $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l \le r \le n$$$) — the range considered in the grade concept.

If $$$t_i$$$ equals $$$2$$$, the integers are $$$i$$$ and $$$v$$$ ($$$0 \le value \le 10$$$), — the grade position in the sequence and it's new value, respectively.

It's guaranteed that at least one query is of type $$$1$$$.

For each query of type $$$1$$$ print it's grade concept.

1 3
10
1 1 1
2 1 8
1 1 1

-10
-8

3 3
9 6 5
1 1 3
2 3 7
1 1 3

6
7