Stock Prices Operations

In this problem, you are given the stock prices of $n$ companies and need to process $q$ operations. There are two types of operations:

1. Update Operation: Increase the stock price of a given company by a given amount. The operation is given in the format: 1 i x, which means increase the price of the company at index $i$ (1-indexed) by $x$.

2. Query Operation: Report the maximum difference between stock prices in a specified range. The operation is given in the format: 2 l r, which asks for the difference between the maximum and minimum stock prices among the companies from index $l$ to $r$ (inclusive).

Your task is to simulate these operations. For each query operation, compute the value $$\max_{i=l}^{r}(a_i) - \min_{i=l}^{r}(a_i),$$ where $a_i$ denotes the stock price of the $i$-th company.

Input and output are to be handled through standard input and standard output.

inputFormat

The first line contains two integers $n$ and $q$ — the number of companies and the number of operations. The second line contains $n$ integers representing the initial stock prices. Each of the next $q$ lines contains an operation in one of the following two formats:

• Update operation: 1 i x — increase the stock price of the $i$-th company by $x$.
• Query operation: 2 l r — output the maximum difference between any two stock prices in the range from $l$ to $r$ (inclusive).

outputFormat

For each query operation, output the result on a new line. There should be exactly one output per query.## sample

5 5
10 5 15 10 20
2 1 5
1 3 5
2 1 5
1 2 3
2 1 3

15
15
12