Concert Fan Support

There are \(n\) fans seated in a row at a concert. The \(i\)-th fan has a support value \(a_i\). When the spotlight shines on an interval \([l, r]\) (1-indexed), it produces an effective support value defined as:

\[ \text{Effective Support} = \left(\sum_{i=l}^{r}a_i\right)\times\max_{l\le i\le r}a_i \]

In order to cheer better, a fan may change his/her support value. You are given \(q\) operations. Each operation is either an update operation or a query operation:

• Update operation: 1 i x meaning change the support value of the \(i\)-th fan to \(x\).
• Query operation: 2 l r meaning output the effective support value for the interval \([l, r]\).

Help Xiaolin to calculate the effective support value for each spotlight query.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1\le n,q\le 10^5)\) denoting the number of fans and the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\) --- the initial support values of the fans.

Then \(q\) lines follow. Each line represents an operation and is in one of the following two formats:

• 1 i x \( (1 \le i \le n, 1 \le x \le 10^9)\): update the support value of the \(i\)-th fan to \(x\).
• 2 l r \( (1 \le l \le r \le n)\): output the effective support value on the interval \([l, r]\).

outputFormat

For each query operation (i.e. operations of the form 2 l r), print a single integer representing the effective support value of the given interval.

sample

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

75
160
150