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:
/**
 * Created by Aminul on 5/20/2018.
 */

import java.io.*;
import java.util.*;

public class CF455D_clean {
    public static void main(String[] args) {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt();

        mainTreap = new ImplicitTreap();
        treaps = new ImplicitTreap[n+1];
        for (int i = 0; i <= n; i++) {
            treaps[i] = new ImplicitTreap();
        }

        Node temp, temp2;
        for (int i = 1; i <= n; i++) {
            int x = in.nextInt();
            temp = mainTreap.addLast(x);
            temp2 = treaps[x].addLast(x);
            temp2.link = temp;
            temp.link = temp2;
        }


        int lastAns = 0, l = 0, r = 0, k = 0;
        int q = in.nextInt();
        for (int i = 0; i < q; i++) {
            int type = in.nextInt();
            if (type == 1) {
                l = in.nextInt(); r = in.nextInt();
                l = (l + lastAns - 1) % n + 1;
                r = (r + lastAns - 1) % n + 1;
                if (l > r) {
                    int tmp = l;l = r;r = tmp;
                }
                update(l, r);
            } else {
                l = in.nextInt(); r = in.nextInt(); k = in.nextInt();
                l = (l + lastAns - 1) % n + 1;
                r = (r + lastAns - 1) % n + 1;
                k = (k + lastAns - 1) % n + 1;
                if (l > r) {
                    int tmp = l;l = r;r = tmp;
                }
                pw.println(lastAns = query(l, r, k));
            }
        }
        pw.close();
    }

    static ImplicitTreap mainTreap, treaps[];

    static void update(int l, int r){
        Node del = mainTreap.remove(r), del2;
        int v = del.value;
        int idx = cal(treaps[v].root, r);
        del2 = treaps[v].remove(idx);
        mainTreap.add(l, del);
        int k = cal(treaps[v].root, l);
        treaps[v].add(k+1, del2);
    }

    static int query(int l, int r, int k){
        return cal(treaps[k].root, r) - cal(treaps[k].root, l-1);
    }


    static int cal(Node t, int k){
        int r = 0;
        while (t != null){
            int idx = mainTreap.indexOf(t.link);
            if(idx <= k){
                r += size(t.left)+1;
                t = t.right;
            }
            else t = t.left;
        }
        return r;
    }

    static class Node {
        int size, value;
        double priority;
        Node left, right, parent, link;

        public Node(int val) {
            value = val;
            size = 1;
            priority = Math.random();
        }
    }

    static class NodePair {
        Node left, right;
        public NodePair(Node l, Node r) {
            left = l;
            right = r;
        }
    }

    static int size(Node t) {
        if (t == null) return 0;
        else return t.size;
    }

    static class ImplicitTreap { // This treap works with 1-based indexing //
        Node root;

        public int size() {
            return size(root);
        }

        int size(Node t) {
            if (t == null) return 0;
            else return t.size;
        }

        private void update(Node t) {
            if (t != null){
                t.size = size(t.left) + 1 + size(t.right);
                t.parent = null;
            }
        }

        public void setParent(Node child, Node parent){
            if(child != null) child.parent = parent;
        }

        public Node addLast(int val){
            return add(size()+1, val);
        }

        public Node add(int index, int val) {
            NodePair n = split(root, index-1);
            Node newNode = new Node(val);
            root = merge(n.left, merge(newNode, n.right));
            return newNode;
        }

        public Node addLast(Node val){
            return add(size()+1, val);
        }

        public Node add(int index, Node val) {
            NodePair n = split(root, index-1);
            root = merge(n.left, merge(val, n.right));
            return val;
        }


        public Node remove(int k) {
            NodePair res1 = split(root, k - 1);
            NodePair res2 = split(res1.right, 1);
            root = merge(res1.left, res2.right);
            return res2.left;
        }

        public int indexOf(Node cur){
            Node fa = cur.parent;
            int ret = size(cur.left) + 1;
            while(fa != null) {
                if(cur != fa.left ) ret += size(fa.left)+1;
                cur = fa; fa = cur.parent;
            }
            return ret;
        }

        public int get(int k) {
            if (k > size(root) || k <= 0) throw new IllegalArgumentException();
            return get(root, k);
        }

        // auxiliary function for get
        int get(Node n, int k) {
            if (n == null) return -1;
            int key = size(n.left) + 1;
            if (key > k) return get(n.left, k);
            else if (key < k) return get(n.right, k - key);
            return n.value;
        }

        public void modify(int key, int val) {
            modify(root, key, val);
        }

        // auxiliary method for modify
        private void modify(Node n, int k, int val) {
            int key = size(n.left) + 1;
            if (key == k) n.value = val;
            else if (k < key) modify(n.left, k, val);
            else modify(n.right, k - key, val);
            update(n);
        }

        private NodePair split(Node n, int k) {
            NodePair res = new NodePair(null, null);
            if (n == null) return res;
            int key = size(n.left) + 1;
            if (key > k) {
                res = split(n.left, k);
                n.left = res.right; setParent(res.right, n);
                res.right = n;
            } else {
                res = split(n.right, k - key);
                n.right = res.left; setParent(res.left, n);
                res.left = n;
            }
            //update(n);
            update(res.left);
            update(res.right);
            return res;
        }

        Node temp;
        private Node merge(Node t1, Node t2) {
            if (t1 == null) return t2;
            else if (t2 == null) return t1;
            Node newRoot = null;
            if (t1.priority > t2.priority) {
                temp = merge(t1.right, t2);
                t1.right = temp;   setParent(temp, t1);
                newRoot = t1;
            } else {
                temp = merge(t1, t2.left);
                t2.left = temp;    setParent(temp, t2);
                newRoot = t2;
            }
            update(newRoot);
            return newRoot;
        }

        public void clear() {
            root = null;
        }

        public void print() {
            print(root);
            if (root != null) System.out.println();
        }

        private void print(Node t) {
            if (t == null) return;
            print(t.left);
            System.out.print(t.value +" ");
            print(t.right);
        }

    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }
}