Omega Function Queries

In this problem, you are given an array a of length n representing the yield of n fields, arranged sequentially. The yield of the i-th field is given by a[i] and these fields are managed by the autumn deities. They derive the annual yield based on a compound function \(\Omega(l,r)\) defined on any segment of the fields. The definitions are as follows:

[ \Alpha(l,r)=\max_{l\leq i\leq r}\Big{i\times\Big[ a_i = \max_{l\leq j\leq r}{a_j}\Big]\Big} ]

Here, the Iverson bracket [P] equals 1 if proposition P is true, and 0 otherwise, so \(\Alpha(l,r)\) is the largest index in the interval \([l, r]\) where the field achieves the maximum yield.

[ \Beta(l,r)= \max_{l\leq i\leq r}\Big{\min_{1\leq j\leq i}{\Alpha(j,i)}\Big} - \min_{l\leq i\leq r}\Big{\max_{1\leq j\leq i}{\Alpha(j,i)}\Big} ]

and

[ \Omega(l,r)= \min_{l\leq i\leq r}\Big{\min_{i\leq j\leq r}{|\Beta(i,j)|}\Big} ]

Notice that for any segment \([l, r]\), when \(i=j\) we have \(\Beta(i,i)=0\); thus, \(\Omega(l,r)=0\) for any \(l\) and \(r\).

You are also given q operations on the array. The operations are of two types:

1. 1 x y: Increase each of a[1] to a[x] by y.
2. 2 l r: Query the value of \(\Omega(l,r)\) on the segment from l to r.

Since \(\Omega(l,r)\) is always 0, every query of type 2 should output 0.

inputFormat

The first line contains two integers n and q (\(1 \leq n, q \leq 10^5\)), representing the number of fields and the number of operations.

The second line contains n integers, the i-th of which is a[i].

Each of the following q lines describes an operation in one of the following two formats:

• 1 x y: Increase each of a[1] to a[x] by y (\(1 \leq x \leq n, |y| \leq 10^9\)).
• 2 l r: Query the value of \(\Omega(l,r)\) for the segment from l to r (\(1 \leq l \leq r \leq n\)).

outputFormat

For each query of type 2, output a single line containing the value of \(\Omega(l,r)\). Since \(\Omega(l,r)=0\) for any segment, the output will always be 0.

sample

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

0
0
0

</p>