Circular RMQ

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a circular array under circular range addition and circular range-minimum queries.

Input

Line 1 contains $n$, line 2 contains $a_0,\ldots,a_{n-1}$, and line 3 contains $m$. Each operation line has two or three integers.

• l r: query the minimum on the circular interval from $l$ to $r$.
• l r v: add $v$ to that circular interval.

If $l>r$, the interval is $l,\ldots,n-1,0,\ldots,r$.

Output

Print the minimum for every operation line containing exactly two integers.

Subtasks

• 20 points: $n,m\le50$.
• 30 points: $n,m\le5000$.
• 50 points: $1\le n\le2\cdot10^5$, $0\le m\le2\cdot10^5$, $|a_i|,|v|\le10^6$.

Examples

Input

4
1 2 3 4
4
3 0
3 0 -1
0 1
2 1

Output

1
0
0

Explanation

The circular interval from 3 to 0 contains positions 3 and 0, whose initial minimum is 1. After adding $-1$ there, the next two minimum queries both return 0.