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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.math.BigInteger;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Vadim Semenov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskD solver = new TaskD();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskD {
    private static final int MAGIC = 333;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int counter = in.nextInt();
        int[][] elements = new int[MAGIC][MAGIC];
        int[] head = new int[MAGIC];
        int[] tail = new int[MAGIC];
        Arrays.fill(tail, -1);
        int[][] cnt = new int[MAGIC][counter + 1];
        int currentBlock = 0;
        for (int i = 0; i < counter; ++i) {
            int x = in.nextInt();
            if (tail[currentBlock] + 1 == MAGIC) {
                currentBlock++;
            }
            elements[currentBlock][++tail[currentBlock]] = x;
            cnt[currentBlock][x]++;
        }
        int queryCounter = in.nextInt();
        int lastAns = 0;
        for (int query = 0; query < queryCounter; ++query) {
            int type = in.nextInt();
            if (type == 1) {
                int li = (in.nextInt() + lastAns - 1) % counter;
                int ri = (in.nextInt() + lastAns - 1) % counter;
                if (li > ri) {
                    int tmp = li; li = ri; ri = tmp;
                }
                int first = li / MAGIC;
                int fpos = li % MAGIC;
                int second = ri / MAGIC;
                int spos = ri % MAGIC;

                if (first == second) {
                    int tmp = elements[first][(head[first] + spos) % MAGIC];
                    for (int i = (head[first] + spos) % MAGIC; i != (head[first] + fpos) % MAGIC; i = pred(i)) {
                        elements[first][i] = elements[first][pred(i)];
                    }
                    elements[first][(head[first] + fpos) % MAGIC] = tmp;
                } else {
                    int tmp = elements[first][tail[first]];
                    cnt[first][tmp]--;
                    for (int i = tail[first]; i != (head[first] + fpos) % MAGIC; i = pred(i)) {
                        elements[first][i] = elements[first][pred(i)];
                    }
                    for (int block = first + 1; block < second; ++block) {
                        // removeLast
                        int tmp2 = elements[block][tail[block]];
                        tail[block] = pred(tail[block]);
                        cnt[block][tmp2]--;
                        // addFirst
                        head[block] = pred(head[block]);
                        elements[block][head[block]] = tmp;
                        cnt[block][tmp]++;
                        //
                        tmp = tmp2;
                    }
                    int tmp2 = elements[second][(head[second] + spos) % MAGIC];
                    cnt[second][tmp2]--;
                    elements[first][(head[first] + fpos) % MAGIC] = tmp2;
                    cnt[first][tmp2]++;
                    for (int i = (head[second] + spos) % MAGIC; i != head[second]; i = pred(i)) {
                        elements[second][i] = elements[second][pred(i)];
                    }
                    elements[second][head[second]] = tmp;
                    cnt[second][tmp]++;
                }
            } else if (type == 2) {
                int li = (in.nextInt() + lastAns - 1) % counter;
                int ri = (in.nextInt() + lastAns - 1) % counter;
                if (li > ri) {
                    int tmp = li; li = ri; ri = tmp;
                }
                int ki = (in.nextInt() + lastAns - 1) % counter + 1;
                int first = li / MAGIC;
                int fpos = li % MAGIC;
                int second = ri / MAGIC;
                int spos = ri % MAGIC;
                lastAns = 0;

                if (first == second) {
                    for (int i = (head[first] + fpos) % MAGIC; i != (head[first] + spos) % MAGIC; i = succ(i)) {
                        if (elements[first][i] == ki) lastAns++;
                    }
                    if (elements[first][(head[first] + spos) % MAGIC] == ki) lastAns++;
                } else {
                    for (int i = (head[first] + fpos) % MAGIC; i != tail[first]; i = succ(i)) {
                        if (elements[first][i] == ki) lastAns++;
                    }
                    if (elements[first][tail[first]] == ki) lastAns++;
                    for (int block = first + 1; block < second; ++block) {
                        lastAns += cnt[block][ki];
                    }
                    for (int i = head[second]; i != (head[second] + spos) % MAGIC; i = succ(i)) {
                        if (elements[second][i] == ki) lastAns++;
                    }
                    if (elements[second][(head[second] + spos) % MAGIC] == ki) lastAns++;
                }
                out.println(lastAns);
            } else throw new AssertionError(type);
        }
    }

    private static final int succ(int i) {
        return (i + 1) % MAGIC;
    }

    private static final int pred(int i) {
        return (i - 1 + MAGIC) % MAGIC;
    }
}

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(readLine());
        }
        return tokenizer.nextToken();
    }

    public String readLine() {
        String line = null;
        try {
            line = reader.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return line;
    }
}