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.io.*;
import java.util.*;

public class Main {

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

        new Main().solve();

    }

    int mod = 1000000007;

    PrintWriter out;

    int n;
    int m;

    ArrayList<Integer>[] g;

    int blocks;

    void solve() throws IOException {

        //Reader in = new Reader("in.txt");
        //out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
        Reader in = new Reader();
        out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );

        //BufferedReader br = new BufferedReader( new FileReader("in.txt") );
        //BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );

        n = in.nextInt();

        a = new int[n];

        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();

        blocks = (int) Math.sqrt(n);
        blocksCnt = n/blocks;
        maxSize = blocks+1000;

        if (n%blocks != 0)
            blocksCnt++;

        t = new int[n/blocks+1][maxSize];
        met = new int[n/blocks+1][100010];
        size = new int[n/blocks+1];

        int lastans = 0;

        build();
//        System.err.println(a[99]);
//        remove(1);
//        System.err.println(get(1));
//        insert(1, 10);
//        System.err.println(get(1));


        int m = in.nextInt();

        for (int i = 0; i < m; i++) {

            int c = in.nextInt();

            if (c == 1) {

                int l = in.nextInt();
                int r = in.nextInt();
                l = (l+lastans-1)%n;
                r = (r+lastans-1)%n;

                //System.err.println(l+" "+r);

                if (l > r) {

                    int tmp = l;
                    l = r;
                    r = tmp;
                }


                if (l < r)
                    shift(l, r);
            }
            else {

                int l = in.nextInt();
                int r = in.nextInt();
                int k = in.nextInt();

                l = (l+lastans-1)%n;
                r = (r+lastans-1)%n;
                k = (k+lastans-1)%n+1;

                if (l > r) {

                    int tmp = l;
                    l = r;
                    r = tmp;
                }

                //System.err.println(l+" "+r+" "+k);

                int res = query(l, r, k);
                lastans = res;

                out.println(res);
            }

        }

//        rebuild();
//
//        for (int i = 0; i < n; i++)
//            out.print(a[i]+" ");

        //System.err.println(get(3));

        out.flush();
        out.close();
    }

    int[] a;
    int[][] t;
    int[] size;
    int[][] met;
    int maxSize;
    int blocksCnt;

    void build() {

        for (int i = 0; i < n; i++) {

            t[i/blocks][i%blocks] = a[i];
            met[i/blocks][a[i]]++;
            size[i/blocks]++;
        }
    }

    void rebuild() {

        int pos = 0;

        for (int i = 0; i < blocksCnt; i++)
            for (int j = 0; j < size[i]; j++)
                a[pos++] = t[i][j];

//        for (int i = 0; i < n; i++)
//            a[i] = get(i);

        for (int i = 0; i < n/blocks+1; i++)
            Arrays.fill(met[i], 0);

        Arrays.fill(size, 0);
        build();
    }

    int get(int pos) {

        int b = 0;
        int sum = size[0];

        while (sum <= pos) {

            b++;
            sum += size[b];
        }

        return t[b][size[b] - (sum - pos)];
    }

    void insert(int pos, int x) {

        int sum = size[0];
        int b = 0;

        while (sum <= pos) {

            //System.err.println(sum+" "+size[b]+" "+b);

            b++;
            sum += size[b];
        }

        int of = size[b] - (sum - pos);
        int last = size[b];
        size[b]++;
        met[b][x]++;

        while (last > of) {

            t[b][last] = t[b][last-1];
            last--;
        }

        t[b][of] = x;

        if (size[b] >= maxSize)
           rebuild();
    }

    void remove(int pos) {

        int b = 0;
        int sum = size[b];

        while (sum <= pos) {

            b++;
            sum += size[b];
        }

        int of = size[b] - (sum - pos);
        int last = size[b];

        size[b]--;
        met[b][t[b][of]]--;

        while (of < last-1) {

            t[b][of] = t[b][of+1];
            of++;
        }
    }

    int query(int l, int r, int x) {

        int res = 0;

        int lb = 0;
        int rb = 0;

        int sum1 = size[lb];
        int sum2 = size[rb];

        while (sum1 <= l) {

            lb++;
            sum1 += size[lb];
        }

        while (sum2 <= r) {

            rb++;
            sum2 += size[rb];
        }

        int ofl = size[lb] - (sum1 - l);
        int ofr = size[rb] - (sum2 - r);

        for (int i = lb+1; i < rb; i++)
            res += met[i][x];

        if (lb == rb) {

            for (int i = ofl; i <= ofr; i++)
                if (t[rb][i] == x)
                    res++;

            return res;
        }

        for (int i = ofl; i < size[lb]; i++)
            if (t[lb][i] == x)
                res++;

        for (int i = 0; i <= ofr; i++)
            if (t[rb][i] == x)
                res++;

        return res;
    }

    void shift(int l , int r) {

        int x = get(r);
        remove(r);
        insert(l, x);
    }

    class Pair implements Comparable<Pair>{

        int a;
        int b;


        Pair(int a, int b) {

            this.a = a;
            this.b = b;
        }

        public int compareTo(Pair p) {

            if (a > p.a)
                return 1;

            if (a < p.a)
                return -1;

            if (b > p.b)
                return 1;

            if (b < p.b)
                return -1;

            return 0;
        }
    }

    class Reader {

        BufferedReader  br;
        StringTokenizer tok;

        Reader(String file) throws IOException {
            br = new BufferedReader( new FileReader(file) );
        }

        Reader() throws IOException {
            br = new BufferedReader( new InputStreamReader(System.in) );
        }

        String next() throws IOException {

            while (tok == null || !tok.hasMoreElements())
                tok = new StringTokenizer(br.readLine());
            return tok.nextToken();
        }

        int nextInt() throws NumberFormatException, IOException {
            return Integer.valueOf(next());
        }

        long nextLong() throws NumberFormatException, IOException {
            return Long.valueOf(next());
        }

        double nextDouble() throws NumberFormatException, IOException {
            return Double.valueOf(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

    }

}