52_C. Circular RMQ
You are given circular array a0, a1, ..., an - 1. There are two types of operations with it: 

  * inc(lf, rg, v) — this operation increases each element on the segment [lf, rg] (inclusively) by v; 
  * rmq(lf, rg) — this operation returns minimal value on the segment [lf, rg] (inclusively). 



Assume segments to be circular, so if n = 5 and lf = 3, rg = 1, it means the index sequence: 3, 4, 0, 1.

Write program to process given sequence of operations.

Input

The first line contains integer n (1 ≤ n ≤ 200000). The next line contains initial state of the array: a0, a1, ..., an - 1 ( - 106 ≤ ai ≤ 106), ai are integer. The third line contains integer m (0 ≤ m ≤ 200000), m — the number of operartons. Next m lines contain one operation each. If line contains two integer lf, rg (0 ≤ lf, rg ≤ n - 1) it means rmq operation, it contains three integers lf, rg, v (0 ≤ lf, rg ≤ n - 1; - 106 ≤ v ≤ 106) — inc operation.

Output

For each rmq operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Examples

Input

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


Output

1
0
0
```python
import math,sys,bisect,heapq,os
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
from functools import lru_cache
#sys.setrecursionlimit(200000000)
int1 = lambda x: int(x) - 1
def input(): return sys.stdin.readline().rstrip('\r\n')
#input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
aj = lambda: list(map(int, input().split()))
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
#MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

def solve():


	n=int(input())
	a=list(map(int,input().split()))

	class st:
		def __init__(self, size):
			n = size
			h = int(math.log2(n-1))+1 if n>1 else 0
			N = 2**h
			self.t = [float('inf')]*(2*N)
			self.d = [0]*N
			self.N = N
			self.h = h
	    
		def apply(self, p, value):
			self.t[p] += value
			if (p < self.N):
				self.d[p] += value
	    
		def build(self, p):
			t = self.t
			d = self.d
			while p > 1:
				p >>= 1
				t[p] = min(t[p<<1], t[p<<1|1]) + d[p]
	    
		def rebuild(self):
			t = self.t
			for p in reversed(range(1, self.N)):
				t[p] = min(t[p<<1], t[p<<1|1])
	    
		def push(self, p):
			d = self.d
			for s in range(self.h, 0, -1):
				i = p >> s
				if d[i] != 0:
					self.apply(i<<1, d[i])
					self.apply(i<<1|1, d[i])
					d[i] = 0
	    
		def inc(self, l, r, value):
			if l > r:
				return

			l += self.N
			r += self.N+1
			l0, r0 = l, r
			while l < r:
				if l & 1:
					self.apply(l, value)
					l += 1
				if r & 1:
					r -= 1
					self.apply(r, value)
				l >>= 1
				r >>= 1
			self.build(l0)
			self.build(r0 - 1)
	    
		def query(self, l, r):
			if l > r:
				return float('inf')
			t = self.t
			l += self.N
			r += self.N+1
			self.push(l)
			self.push(r - 1)
			res = float('inf')
			while l < r:
				if l & 1:
					res = min(res, t[l])
					l += 1
				if r & 1:
					r -= 1
					res = min(t[r], res)
				l >>= 1
				r >>= 1
			return res

	se=st(n)
	N=se.N
	for i in range(n):
		se.t[i+N]=a[i]
	se.rebuild()

	q=int(input())
	for i in range(q):
		b=list(map(int,input().split()))
		if len(b)==2:
			l=b[0]
			r=b[1]
			if l>r:
				print(min(se.query(l,n-1),se.query(0,r)))
			else:print(se.query(l,r))
		else:
			l=b[0]
			r=b[1]
			v=b[2]
			if l>r:
				se.inc(0,r,v)
				se.inc(l,n-1,v)
			else:se.inc(l,r,v)

		


try:
	#os.system("online_judge.py")
	sys.stdin = open('input.txt', 'r') 
	sys.stdout = open('output.txt', 'w')
except:
	pass

solve()
```