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 java.io.*;
import java.util.*;
import java.math.*;
 
public class Main{ 
    
    static boolean ONLINE_JUDGE = false;//change before submit
    static Fast f = new Fast();
    static PrintWriter out = new PrintWriter(System.out); 
    static boolean TEST_CASES = false;

    
    static void solve(int TC_NO) {

      
      int n = ri();
      int[] a = ra(n);

      int m = ri();
      
      SegTreeLazy stl = new SegTreeLazy(a);

      while(m-->0){
         
         String[] token = rS().split(" ");

         int l = Integer.parseInt(token[0]) + 1;//to make 1-based
         int r = Integer.parseInt(token[1]) + 1;

         if(token.length==3){ //update operation
           
           int val = Integer.parseInt(token[2]);
           
           if(l>r) {
            stl.range_update(l,n,val);
            stl.range_update(1,r,val);
           }
           else {
            stl.range_update(l,r,val);
           }
           continue;
         }


         if(l>r){
           long part1 = stl.range_query(l,n);
           long part2 = stl.range_query(1,r);

           out.println(stl.opq(part1,part2));
           continue;
         }


         out.println(stl.range_query(l,r));
      } 


      /* WARNING : change [ONLINE_JUDGE = false] before SUBMIT */ 
    }

    static class SegTreeLazy{
 

        private long[] arr;
        private long[] change;


        public SegTreeLazy(int n) {

            int extra = (Integer.highestOneBit(n)<<1)-n;

            if(extra==n) extra = 0;

            arr = new long[(n+extra)<<1];
            change = new long[(n+extra)<<1];

            Arrays.fill(arr,ie());
        
        }

        public SegTreeLazy(int[] a) {
            
            this(a.length);

            int start = arr.length>>1;
            for(int i = 0; i < a.length; i++) {
              arr[start+i] = a[i];
            }

            build();
        
        }

        private long ie() {

            //return 0;//for [sum,xor,max,or] opqeration 
            return Long.MAX_VALUE;    
        
        }
         
        //opqerator for query opqeration on segments
        public long opq(long x, long y) {

            return Math.min(x,y);

        }

        //opqerator for update opqeration on segments
        private long opu(long x, long y) {

           return x + y;

        }

        private void build() {
           
            int cur  = (arr.length-1)>>1;

            while(cur>0){

               arr[cur] = opq(arr[left_child(cur)],arr[right_child(cur)]);
               
               cur--;
            }
        
        }

        private int parent(int i) {

           if(i==1) return -1;

           return i>>1;
        
        }

        private int left_child(int i) {

           return i<<1;
        
        }

        private int right_child(int i) {

           return (i<<1)|1;
        
        }


        private void propagate(int ind) {
            
            int l = left_child(ind);
            int r = right_child(ind);
            
            if(l<arr.length) change[l] = opu(change[l],change[ind]);    
            
            if(r<arr.length) change[r] = opu(change[r],change[ind]);
            
            if(r>=arr.length) arr[ind] = opu(arr[ind],change[ind]); //leaf node 
            change[ind] = 0;
        
        }

        private void update(int ind){

            int l = left_child(ind);
            int r = right_child(ind);
            
            if(r<arr.length)
            arr[ind] = opq(opu(arr[l],change[l]),opu(arr[r],change[r]));
         
        }

        public void range_update(int ql, int qr, int val) {

           range_update(ql,qr,1,arr.length>>1,1,val);

        }
         
        /*Here [ql,qr] represents range to be queried and [l,r] represents current segment range and cur represents the index of current segment*/
        public void range_update(int ql,int qr,int l,int r,int cur, int val) {
            
            //no overlap get out-of-recursion
            if(ql>r || qr<l) return;

            //complete overlap update change
            if(ql<=l && r<=qr) {
              change[cur] = opu(change[cur],val);
              return; 
            }

            //partial-overlap
            //first propagate the change to children

            propagate(cur);

            int mid = l+((r-l)>>1);
            
            range_update(ql,qr,l,mid,left_child(cur),val);
            range_update(ql,qr,mid+1,r,right_child(cur),val);

            update(cur);
        
        }

        public long range_query(int ql,int qr) {

           return range_query(ql,qr,1,arr.length>>1,1);

        } 
         
        /*Here [ql,qr] represents range to be queried and [l,r] represents current segment range and cur represents the index of current segment*/
        public long range_query(int ql,int qr,int l,int r,int cur) {
            
            //no overlap return identity element
            if(ql>r || qr<l) return ie();

            //complete overlap return ans for cur segment and its change
            if(ql<=l && r<=qr) return opu(arr[cur],change[cur]);
            
            //partial overlap
            //first propagate change to children

            propagate(cur);

            int mid = l+((r-l)>>1);

            long leftSeg =  range_query(ql,qr,l,mid,left_child(cur));
            long rightSeg = range_query(ql,qr,mid+1,r,right_child(cur));

            update(cur);
            
            return opq(leftSeg,rightSeg);
         
        }
    
    } 
    
    static class MMath {
      
      //O(1)
      static int mod(long a, int m) {
          
         a = a - (a/m) * m;
             
         return a < 0? (int)(a+m): (int)a;

      }
      
      //O(1)
      static long mod(long a, long m){
          
          a = a - (a/m) * m;
             
          return a < 0? (a+m): a;
       
      }
      
      //O(1)
      static int madd(long a, long b, int m) {
            
           a = mod(a,m);
           b = mod(b,m);

           return mod(a+b+2l*m,m);

      }
      
      //O(LOG(a))
      static int mprod(long a, long b, int m) {

            int result = 0;

            while(a>0){

                if(mod(a,2)==1) 
                  result = madd(result,b,m);

                b = madd(b,b,m);
                a = a>>1; 
            }

            return result;

      }
       
      //O(LOG(N)) 
      static int bexpo(int x, int n) {
          
          int result = 1;
          
          while(n>0)
          {
              if(mod(n,2) == 1)
                  result = result * x;
              x = x*x;
              n = n>>1;
          
          }

          return result;
       
      }

      //O(LOG(N))
      static int mexpo(long x, long n, int m) {
        
          int result = 1;
          x = mod(x,m);
          
          while(n>0) {
              if(mod(n,2) == 1)
                  result = mprod(result,x,m);
              x = mprod(x,x,m);
              n = n>>1;
          }

          return result;

      }

      //O(LOG(MAX(A,B)))
      static int gcd(int a, int b){

            while(a!=0 && b!=0){
                 
                 if(a>b) a = mod(a,b);
                 
                 else  b = mod(b,a);
            }

            return a+b;   

      }
      
      //O(LOG(MAX(A,B)))
      static int lcm(int a, int b) {
                 
            return a / gcd(a,b) * b;

      }

      //O(LOG(MAX(A,B)))
      static long gcd(long a,long b){
           
            while(a!=0 && b!=0){
                 
                 if(a>b) a = mod(a,b);
                 
                 else  b = mod(b,a);
            }

            return a+b;   
        
      } 

      //O(LOG(MAX(A,B)))
      static long lcm(long a, long b) {
                 
            return a / gcd(a,b) * b;

      }

      /*Used to solve ax+by=gcd(a,b) */
      static int d, x0, y0;//global or static 
      static void extendedEuclid(int a, int b) {
        
        if(b == 0) {
            d = a;
            x0 = 1;
            y0 = 0;
        }
        else {
            extendedEuclid(b, mod(a,b));
            int temp = x0;
            x0 = y0;
            y0 = temp - (a/b)*y0;
        }
      
      }
      
      //O(LOG(MAX(A,B)))
      static int[] eeuclid(int a, int b) {
          
          extendedEuclid(a,b);

          return new int[]{d,x0,y0};

      }

      //modular multiplicative Inverse exists only when A and M are Co-prime
      //O(LOG(MAX(A,M)))
      static int modInverse(int a, int m) {

         extendedEuclid(a,m);

         return mod(x0,m);
             
      }

      //MMI using FLT (applied only when m is prime)
      //O(LOG(M))
      static int modInversePrime(int a,int m) {

            return mexpo(a,m-2,m);

      }

    }

    public static void main(String[] args)throws Exception{

      out = ONLINE_JUDGE? new PrintWriter(new BufferedWriter(new FileWriter("output.txt"))): new PrintWriter(System.out);
      
      if(TEST_CASES){
          
          int t = ri();
          int i = 1;
          while(i<=t){
            solve(i);
            i++;
          }

      }

      else {

        solve(1);
      
      }
      
      out.close();

    }

    static int ri() {

      return f.nextInt();
    
    }

    static long rl() {
 
      return f.nextLong();
    
    }

    static double rd() {

       return f.nextDouble();
    
    }

    static char rc() {
      
       return rs().charAt(0);

    }

    static String rs() {

      return f.next();

    }

    static String rS() {
      
       return f.nextLine();
    
    }

    static int[] ra(int n) {
        
      int[] a = new int[n];
      for(int i = 0;i<n;i++) a[i] = ri();
      return a;
        
    }

    static long[] ral(int n) {
        
      long[] a = new long[n];
      for(int i = 0;i<n;i++) a[i] = rl();
      return a;
        
    }

    static double[] rad(int n) {

      double[] a = new double[n];
      for(int i = 0;i<n;i++) a[i] = rd();
      return a;

    }

    static char[] rac() {

        char[] c = rs().toCharArray();

        return c;

    }
    
    static int[][] rm(int n, int m) {
       
       int[][] mat = new int[n][m];

       for(int i = 0; i < n; i++) mat[i] = ra(m);
       
       return mat;

    }

    static char[][] rmc(int n) {
      
      char[][] cmat = new char[n][];
      
      for(int i = 0; i < n;) cmat[i] = rac();

      return cmat;

    }

    static void sort(int[] a) {

      ArrayList<Integer> list=new ArrayList<>();
      for (int i:a) list.add(i);
      Collections.sort(list);
      for (int i=0; i<a.length; i++) a[i]=list.get(i);

    }
  
    static class Fast{
       public BufferedReader br;
       public StringTokenizer st;
       
       public Fast(){
            try{
                br = ONLINE_JUDGE? (new BufferedReader(new FileReader("input.txt"))):(new BufferedReader(new InputStreamReader(System.in)));
            }
            catch(Exception e){
              throw new RuntimeException(e);
            }
       }
       
       String next(){
            while(st==null || !st.hasMoreTokens()){
                 try{
                      st=new StringTokenizer(br.readLine());
                 }
                 catch(IOException e){
                      throw new RuntimeException(e);
                 }
                 
            }
                 return st.nextToken();
            }
       int nextInt(){
            return Integer.parseInt(next());
       }
   
       long nextLong(){
            return Long.parseLong(next());
       }
   
       double nextDouble(){
            return Double.parseDouble(next());
       }

       String nextLine() 
          { 
              String str = ""; 
              try
              { 
                  str = br.readLine(); 
              } 
              catch (IOException e) 
              { 
                  e.printStackTrace(); 
              } 
              return str; 
          } 
   
    }

    static String gcc(int TC_NO) {

         return "Case #"+TC_NO+": ";

    }

    static boolean isLetter(char c){

      return (64<c && c<91) || (96<c && c<123);
    
    }

}

