For Kele, the most difficult times are when she goes shopping with her good friend Sylvia.

There are $n$ clothing stores in the mall they frequent, numbered from $1$ to $n$. In Kele's aesthetic, each store's clothing has an aesthetic value. Initially, the aesthetic value of the clothing in the $i$-th store is $x_i$. Kele dislikes ambiguity, so all $x_i$ are distinct.

Kele has a special shopping technique: every time she goes shopping, she chooses an interval of indices $[l, r]$ and visits the stores numbered $l, l+1, \dots, r$ in sequence. Initially, Kele's lower bound for aesthetic tolerance is $0$. Whenever she enters a new store, if the aesthetic value of the clothing in that store is strictly greater than her current tolerance, she buys the clothing, and her tolerance becomes the aesthetic value of that store. Otherwise, she does not buy anything in that store. The profit from one shopping trip is the sum of the aesthetic values of all the clothing she buys.

As the saying goes, "great writers steal": clothing stores are no exception. Sometimes, some clothing stores imitate the designs of their competitors. Each imitation event occurs within a continuous range of stores (let's assume the interval is $[l, r]$, and before the imitation, the aesthetic value of the $i$-th store is $a_i$). Initially, the $l$-th store imitates the $(l+1)$-th store, and its aesthetic value changes from $a_l$ to $\max(a_l, a_{l+1})$. Then, the chain reaction begins: when the $(l+1)$-th store realizes it has been imitated, to maintain its competitiveness, it imitates the $(l+2)$-th store, so its aesthetic value becomes $\max(a_{l+1}, a_{l+2})$. This process continues until the $r$-th store is imitated: since the $r$-th store chooses to remain unchanged, the chain reaction ends.

In simple terms, for an imitation event occurring in the interval $[l, r]$, assuming the aesthetic value of the $i$-th store before the event is $a_i$, then after the event, for every store $i$ in $[l, r)$, its aesthetic value becomes $\max(a_i, a_{i+1})$; for all other stores, their aesthetic values remain unchanged.

Now, $m$ events occur in chronological order. There are two types of events:

• Imitation event $1$ $l$ $r$: An imitation event occurs in the interval $[l, r]$.
• Shopping event $2$ $l$ $r$: Kele chooses the interval $[l, r]$ for a shopping trip.

You need to output Kele's profit for each shopping event.

Input

The first line contains two integers $n, m$ ($1 \leq n, m \leq 3 \times 10^5$), representing the number of stores and the number of events.

The second line contains $n$ integers $x_i$ ($1 \leq x_i \leq 10^9$), representing the initial aesthetic value of each store.

The next $m$ lines each contain three integers $t, l, r$ ($t \in \{1, 2\}, 1 \leq l < r \leq n$), describing an event.

It is guaranteed that all elements in the array $x$ are distinct.

Output

For each shopping event, output one integer per line representing Kele's profit.

Examples

Input 1

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

Output 1

13
12
8

Note

Explanation of the sample data:

• During the first shopping trip, Kele chooses to buy clothing from stores $1, 2, 4, 5$, so the profit is $13$.
• After the first imitation event, the aesthetic values of the stores become $3, 3, 4, 5, 5$.
• Kele chooses to buy clothing from stores $1, 3, 4$, so the profit is $12$.
• After the second imitation event, the aesthetic values of the stores become $3, 3, 5, 5, 5$.
• Kele chooses to buy clothing from stores $1, 3$, so the profit is $8$.

Subtasks

Subtask 1 ($7$ points): $1 \leq n, m \leq 5 \times 10^3$.

Subtask 2 ($39$ points): It is guaranteed that for $t = 1$, $l = 1, r = n$.

Subtask 3 ($54$ points): $1 \leq n, m \leq 3 \times 10^5$.