Problem: Serega loves fun. However, everyone has fun in the unique manner. Serega has fun by solving query problems. One day Fedor came up with such a problem.

You are given an array a consisting of n positive integers and queries to it. The queries can be of two types:

  1. Make a unit cyclic shift to the right on the segment from l to r (both borders inclusive). That is rearrange elements of the array in the following manner:a[l], a[l + 1], ..., a[r - 1], a[r] → a[r], a[l], a[l + 1], ..., a[r - 1].
  2. Count how many numbers equal to k are on the segment from l to r (both borders inclusive). 



Fedor hurried to see Serega enjoy the problem and Serega solved it really quickly. Let's see, can you solve it?

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of elements of the array. The second line contains n integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n).

The third line contains a single integer q (1 ≤ q ≤ 105) — the number of queries. The next q lines contain the queries.

As you need to respond to the queries online, the queries will be encoded. A query of the first type will be given in format: 1 l'i r'i. A query of the second type will be given in format: 2 l'i r'i k'i. All the number in input are integer. They satisfy the constraints: 1 ≤ l'i, r'i, k'i ≤ n.

To decode the queries from the data given in input, you need to perform the following transformations:

li = ((l'i + lastans - 1) mod n) + 1; ri = ((r'i + lastans - 1) mod n) + 1; ki = ((k'i + lastans - 1) mod n) + 1.

Where lastans is the last reply to the query of the 2-nd type (initially, lastans = 0). If after transformation li is greater than ri, you must swap these values.

Output

For each query of the 2-nd type print the answer on a single line.

Examples

Input

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


Output

2
1
0
0


Input

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


Output

2
0

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
public class SeregaandFun {
    
    
    
    /************************ SOLUTION STARTS HERE ************************/
    
    
    private static void solve() {
        
        
        int n = nextInt();
        int arr[] = nextIntArray(n);
        int Q = nextInt();

        final int BLOCK_SIZE = (int) (Math.sqrt(n) + 1); 
        LinkedList<Integer> blocks[] = new LinkedList[n / BLOCK_SIZE + 1];
        HashMap<Integer , Integer> freq[] = new HashMap[n / BLOCK_SIZE + 1];
        
        for(int i = 0; i < blocks.length; i++) {
            blocks[i] = new LinkedList<>();
            freq[i] = new HashMap<>();
        }
        for(int i = 0; i < n; i++) {
            blocks[i / BLOCK_SIZE].add(arr[i]);
            freq[i / BLOCK_SIZE].put(arr[i], freq[i / BLOCK_SIZE].getOrDefault(arr[i] , 0) + 1);
        }
        /*
        System.out.println("Block sz = " + BLOCK_SIZE);
        for(int i = 0; i < blocks.length; i++) {
            println("i " + i);
            println(blocks[i]);
            println(freq[i]);
        }
        */
        int ans = 0;
        double q1T = 0;
        double q2T = 0;
        while(Q-->0) {
            int type = nextInt();
            if(type == 1) {
                long start = System.nanoTime();
                int l = ((nextInt() + ans - 1) % n);
                int r = ((nextInt() + ans - 1) % n);
                int L = Math.min(l , r);
                int R = Math.max(l , r);
                boolean add = false;
                for(int i = L / BLOCK_SIZE; i < R / BLOCK_SIZE; i++) {
                    add = true;
                    int toRem = blocks[i].pollLast();
                    int f = freq[i].get(toRem);
                    
                    if(f == 1) freq[i].remove(toRem);
                    else freq[i].put(toRem, f - 1);
                    
                    blocks[i + 1].addFirst(toRem);
                    freq[i + 1].put(toRem, freq[i + 1].getOrDefault(toRem, 0) + 1);
                }
                
                int toRem = blocks[R / BLOCK_SIZE].remove((R % BLOCK_SIZE) + (add ? 1 : 0));
                int f = freq[R / BLOCK_SIZE].get(toRem);
                
                if(f == 1) freq[R / BLOCK_SIZE].remove(toRem);
                else freq[R / BLOCK_SIZE].put(toRem, f - 1);

                blocks[L / BLOCK_SIZE].add(L % BLOCK_SIZE, toRem);
                freq[L / BLOCK_SIZE].put(toRem, freq[L / BLOCK_SIZE].getOrDefault(toRem, 0) + 1);
                q1T += (System.nanoTime() - start) / 1e9;
            } else {
                long start = System.nanoTime();
                int l = ((nextInt() + ans - 1) % n);
                int r = ((nextInt() + ans - 1) % n);
                int L = Math.min(l , r);
                int R = Math.max(l , r);
                int K = ((nextInt() + ans - 1) % n) + 1;
                int cnt = 0;
                for(ListIterator<Integer> it =  blocks[L / BLOCK_SIZE].listIterator(L % BLOCK_SIZE); L <= R && L % BLOCK_SIZE != 0; L++)
                    cnt += it.next().intValue() == K ? 1 : 0;
                for(ListIterator<Integer> it = blocks[R / BLOCK_SIZE].listIterator((R % BLOCK_SIZE) + 1); R >= L && (R + BLOCK_SIZE) % BLOCK_SIZE != BLOCK_SIZE - 1; R--)
                    cnt += it.previous().intValue() == K ? 1 : 0;
                
                for(; L < R; L += BLOCK_SIZE)
                    cnt += freq[L / BLOCK_SIZE].getOrDefault(K, 0);
                
                q2T += (System.nanoTime() - start) / 1e9;
                println(ans = cnt);
            }
        }
        
        if(n == 100000)
            println("Q1T " + q1T + " q2T " + q2T);
            
    }
    
    
    static void solve2() {
        int n = nextInt();
        int arr[] = nextIntArray(n);
        int Q = nextInt();

        final int BLOCK_SIZE = (int) (Math.sqrt(n) + 1); 
        
        int blocks[][] = new int[n / BLOCK_SIZE + 1][BLOCK_SIZE];
        int offset[] = new int[n / BLOCK_SIZE + 1];
        int aux[] = new int[BLOCK_SIZE];
        int freq[][] = new int[n / BLOCK_SIZE + 1][n + 1];
        
        for(int i = 0; i < n; i++) {
            blocks[i / BLOCK_SIZE][i % BLOCK_SIZE] = arr[i];
            freq[i / BLOCK_SIZE][arr[i]]++;
        }
        
        int ans = 0;
        while(Q-->0) {
            int type = nextInt();
            if(type == 1) {
                int l = ((nextInt() + ans - 1) % n);
                int r = ((nextInt() + ans - 1) % n);
                int L = Math.min(l , r);
                int R = Math.max(l , r);
                // System.out.println("1 " + L + " " + R);
                int exit = -1;
                
                if(offset[L / BLOCK_SIZE] != 0) {
                    for(int i = 0; i < BLOCK_SIZE; i++)
                        aux[i] = blocks[L / BLOCK_SIZE][(offset[L / BLOCK_SIZE] + i) % BLOCK_SIZE];
                    System.arraycopy(aux, 0, blocks[L / BLOCK_SIZE], 0, BLOCK_SIZE);
                    offset[L / BLOCK_SIZE] = 0;
                }
                
                if(L / BLOCK_SIZE == R / BLOCK_SIZE) {
                    int prev = blocks[L / BLOCK_SIZE][L % BLOCK_SIZE];
                    for(int i = L % BLOCK_SIZE + 1; i <= R % BLOCK_SIZE; i++) {
                        int t = blocks[L / BLOCK_SIZE][i];
                        blocks[L / BLOCK_SIZE][i] = prev;
                        prev = t;
                    }
                    blocks[L / BLOCK_SIZE][L % BLOCK_SIZE] = prev;
                }
                else {   // move L
                    int qu = L / BLOCK_SIZE;
                    int re = L % BLOCK_SIZE;
                    exit = blocks[qu][BLOCK_SIZE - 1];
                    
                    freq[qu][exit]--;
                    /*
                    int f = freq[qu].get(exit);
                    
                    if(f == 1) freq[qu].remove(exit);
                    else freq[qu].put(exit, f - 1);
                    */
                    for(int i = BLOCK_SIZE - 1; i > re; i--)
                        blocks[qu][i] = blocks[qu][i - 1];
                    blocks[qu][re] = blocks[R / BLOCK_SIZE][(offset[R / BLOCK_SIZE] + R) % BLOCK_SIZE];
                    freq[qu][blocks[qu][re]]++;
                    for(int i = L / BLOCK_SIZE + 1; i < R / BLOCK_SIZE; i++) {
                        offset[i] = (offset[i] - 1 + BLOCK_SIZE) % BLOCK_SIZE;
                        int next = blocks[i][offset[i]];
                        blocks[i][offset[i]] = exit;
                        freq[i][exit]++;
                        exit = next;
                        freq[i][exit]--;
                        
                        /*
                        f = freq[i].get(exit);
                        
                        if(f == 1) freq[i].remove(exit);
                        else freq[i].put(exit, f - 1);
                        */
                    }
                    

                    if(offset[R / BLOCK_SIZE] != 0) {
                        for(int i = 0; i < BLOCK_SIZE; i++)
                            aux[i] = blocks[R / BLOCK_SIZE][(offset[R / BLOCK_SIZE] + i) % BLOCK_SIZE];
                        System.arraycopy(aux, 0, blocks[R / BLOCK_SIZE], 0, BLOCK_SIZE);
                        offset[R / BLOCK_SIZE] = 0;
                    }
                    
                    freq[R / BLOCK_SIZE][exit]++;
                    int toRem = blocks[R / BLOCK_SIZE][R % BLOCK_SIZE];
                    freq[R / BLOCK_SIZE][toRem]--;
                    for(int i = R % BLOCK_SIZE; i > 0; i--)
                        blocks[R / BLOCK_SIZE][i] = blocks[R / BLOCK_SIZE][i - 1];
                    
                    blocks[R / BLOCK_SIZE][0] = exit;
                    
                }
                /*
                for(int i = 0; i < blocks.length; i++) {
                    System.out.print("i " + i + "  ");
                    System.out.print("bl " + Arrays.toString(blocks[i]));
                    System.out.println("  freq " + freq[i] + "\n");
                }
                */
            } else {
                int l = ((nextInt() + ans - 1) % n);
                int r = ((nextInt() + ans - 1) % n);
                int L = Math.min(l , r);
                int R = Math.max(l , r);
                int K = ((nextInt() + ans - 1) % n) + 1;
                // System.out.println("2 " + L + " " + R + " " + K);
                int cnt = 0;
                for(int idx = L / BLOCK_SIZE; L <= R && L % BLOCK_SIZE != 0; L++)
                    cnt += blocks[idx][(offset[idx] + L) % BLOCK_SIZE] == K ? 1 : 0;
                for(int idx = R / BLOCK_SIZE; R >= L && (R + BLOCK_SIZE) % BLOCK_SIZE != BLOCK_SIZE - 1; R--)
                    cnt += blocks[idx][(offset[idx] + R) % BLOCK_SIZE] == K ? 1 : 0;
                for(; L < R; L += BLOCK_SIZE)
                    cnt += freq[L / BLOCK_SIZE][K];
                
                println(ans = cnt);
            }
        }
    }
    
    /************************ SOLUTION ENDS HERE ************************/
    
    
    
    
    
    /************************ TEMPLATE STARTS HERE **********************/
    
    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
        st     = null;
        solve2();
        reader.close();
        writer.close();
    }
    
    static BufferedReader reader;
    static PrintWriter    writer;
    static StringTokenizer st;
    
    static String next()
    {while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}            
    st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
    static String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}             
    static int    nextInt()   {return Integer.parseInt(next());}
    static long   nextLong()  {return Long.parseLong(next());}     
    static double nextDouble(){return Double.parseDouble(next());}
    static char   nextChar()  {return next().charAt(0);}
    static int[]  nextIntArray(int n)         {int[] a= new int[n];   int i=0;while(i<n){a[i++]=nextInt();}  return a;}
    static long[] nextLongArray(int n)        {long[]a= new long[n];  int i=0;while(i<n){a[i++]=nextLong();} return a;}    
    static int[]  nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;}            
    static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;}            
    static void   print(Object o)  { writer.print(o);  }
    static void   println(Object o){ writer.println(o);}
    
    /************************ TEMPLATE ENDS HERE ************************/
    
}