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
import sys
from math import inf, log2
        
class LazySegmentTree:
    def __init__(self, array, func=min):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        self.process(array)
 
    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])
 
    def push(self, index):
        self.lazy[2*index] += self.lazy[index]
        self.lazy[2*index+1] += self.lazy[index]
        self.data[2 * index] += self.lazy[index]
        self.data[2 * index + 1] += self.lazy[index]
        self.lazy[index] = 0
 
    def build(self, index):
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1]) + self.lazy[index]
            index >>= 1
 
    def query(self, alpha, omega):
        res = self.default
        alpha += self.size
        omega += self.size + 1
        for i in range(len(bin(alpha)[2:])-1, 0, -1):
            self.push(alpha >> i)
        for i in range(len(bin(omega-1)[2:])-1, 0, -1):
            self.push((omega-1) >> i)
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res
 
    def update(self, alpha, omega, value):
        alpha += self.size
        omega += self.size + 1
        l, r = alpha, omega
        while alpha < omega:
            if alpha & 1:
                self.data[alpha] += value
                self.lazy[alpha] += value
                alpha += 1
            if omega & 1:
                omega -= 1
                self.data[omega] += value
                self.lazy[omega] += value
            alpha >>= 1
            omega >>= 1
        self.build(l)
        self.build(r-1)
 

debug=True
lines = sys.stdin.read().split("\n")
lines.pop(-1)
debug=False

n = int(lines.pop(0))
nodes = [int(x) for x in lines.pop(0).split(" ")]
ops = int(lines.pop(0))
segtree = LazySegmentTree(nodes)
counter=1
for line in lines:
    
    values = line.split(" ")
    if len(values) == 2:
        a,b = values
        a=int(a)
        b=int(b)
        if (debug):
            print("===================================")
            print("Consulta de Minimo N "+str(counter)+":")
            print("A es "+str(a))
            print("B es "+str(b))
            print("Resultado:",end="")
        if a <b:
            print(segtree.query(a,b))
        elif a==b:
            print(segtree.query(a%n,a%n))
        else:
            if abs(a-b)== 1:
                print(segtree.query(0, n-1))
            else:
                print(min(segtree.query(a%n,n-1), segtree.query(0,b) ) )
        counter+=1

    else:
        a,b,v = values
        a=int(a)
        b=int(b)
        v=int(v)

        if (debug):
            print("==========")
            #print(segtree)
            print("Update de Rango:")
            print("A es "+str(a))
            print("B es "+str(b))
            print("V es "+str(v))
        
        if a<=b:
            segtree.update(a,b,v)
        else:
            segtree.update(a,n-1,v)
            segtree.update(0,b,v);

