Ozi is an employee in Susky's chocolate store. Ozi is in love with his manager Susky's daughter Maria. Susky is an old-school father: he is not going to let Ozi marry before he believes that Ozi deserves to be his groom. He decides to test Ozi's abilities to see if Ozi has enough skills to deserve his daughter. He establishes a challenging task which is described below:

Susky will give Ozi \(\mathbf{Q}\) orders. There are 2 types of orders. To understand these types, Ozi needs to first grasp the design of the store.

There are \(\mathbf{N}\) types of chocolate, each being displayed in different sections in the Susky's store. Every section has a code from \(\mathbf{0}\) to \(\mathbf{N-1}\). The sections are aligned in a circular fashion such that they are arranged clockwise starting from \(\mathbf{0}\) to \(\mathbf{N-1}\). That is, say that Ozi is at the section \(\mathbf{k}\). For the section \(\mathbf{k+1}\) Ozi needs to walk clockwise, for the section \(\mathbf{k-1}\) Ozi needs to walk counter-clockwise.

• The first type of order is finding the largest price difference between 2 chocolate types among the sections from \(a\) to \(b\), inclusive.
• The second type of order is adding an integer (\(increment\)) to the prices of chocolate types from section \(a\) to \(b\), inclusive.

Note: If \(a\) is bigger than \(b\), Ozi has to walk clockwise from \(a\) until Ozi reaches the section \(b\). So in this case, any chocolate type from \(a\) to \(N-1\) and from \(0\) to \(b\) should be taken into account.

If Ozi can complete the orders, Ozi can happily marry Maria and live a happy life forever... Can you help Ozi to complete the tasks?

Input

In the first line, the number of chocolate types \(\mathbf{N}\) is given.

In the second line, the prices for each of the \(\mathbf{N}\) types are given. (\(\mathbf{P_i}\) for \(i^{th}\) chocholate type)

In the third line, the number of orders \(\mathbf{Q}\) is given.

In the following \(\mathbf{Q}\) lines, each order is given in a separate line:

• Orders that start with 1 have 3 numbers: 1, \(a\), and \(b\). They correspond to the first type of orders explained above.
• Orders that start with 2 have 4 numbers: 2, \(a\), \(b\), and \(increment\). They correspond to the other type of orders explained above.

• \(1 \leq \mathbf{N}, \mathbf{Q} \leq 10^5\)
• \(1 \leq \mathbf{P_i} \leq 10^5\)
• \(0 \leq a, b \leq N - 1\)
• \(-10^3 \leq increment \leq 10^3\)

Output

For output, only print the results for order type 1.

Examples

Input 1:

8
1 2 3 4 5 6 7 8
3
1 3 7
2 2 4 2
1 3 7

Output 1:

4
2

Input 2:

8
1 1 1 1 1 1 1 1
7
1 0 6
2 1 4 1
1 0 5
2 1 5 1
1 0 4
2 1 6 1
1 0 3

Output 2:

0
1
2
3

Explanation

In the first input.

• For the first order, Ozi finds the maximum difference in the prices of chocolates between \(3^{rd}\) and \(7^{th}\) sections, (3 4 5 6 7). The answer for this order is \(7 - 3 = 4\).
• For the second order, Ozi adds \(increment = 2\) to the prices of chocolates between \(2^{nd}\) and \(4^{th}\) sections, (2 3 4). The new prices of the chocolates at the store are 1 4 5 6 5 6 7 8.
• For the third order, Ozi finds the maximum difference in the prices of chocolates between \(3^{rd}\) and \(7^{th}\) sections, (5 6 5 6 7). The answer for this order is \(7 - 5 = 2\).