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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Deque;
import java.util.function.Supplier;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Collection;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.function.Consumer;
import java.util.Objects;
import java.io.Closeable;
import java.io.Writer;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DSeregaAndFun solver = new DSeregaAndFun();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DSeregaAndFun {
        Debug debug = new Debug(true);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int[] a = in.ri(n);
            BlockChain<Sum, Void, Integer, BlockImpl> bc = new BlockChain<>(n, BlockImpl.B, (l, r) -> {
                return BlockImpl.newInstance(a, l, r);
            });
            int q = in.ri();
            int lastans = 0;
            for (int i = 0; i < q; i++) {
                debug.debug("bc", bc);
                int t = in.ri();
                int l = in.ri();
                int r = in.ri();
                if (!debug.enable()) {
                    l = (l + lastans - 1) % n;
                    r = (r + lastans - 1) % n;
                    if (l > r) {
                        int tmp = l;
                        l = r;
                        r = tmp;
                    }
                } else {
                    l--;
                    r--;
                }
                if (t == 1) {
                    Integer last = bc.get(r);
                    bc.delete(r);
                    bc.insert(l, last);
                } else {
                    int k = in.ri();
                    if (!debug.enable()) {
                        k = (k + lastans - 1) % n + 1;
                    }
                    Sum sum = new Sum();
                    sum.x = k;
                    bc.query(l, r, sum);
                    lastans = sum.cnt;
                    out.println(lastans);
                }
            }
        }

    }

    static class Sum {
        int cnt;
        int x;

    }

    static class Pair<A, B> implements Cloneable {
        public A a;
        public B b;

        public Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }

        public String toString() {
            return "a=" + a + ",b=" + b;
        }

        public int hashCode() {
            return a.hashCode() * 31 + b.hashCode();
        }

        public boolean equals(Object obj) {
            Pair<A, B> casted = (Pair<A, B>) obj;
            return Objects.equals(casted.a, a) && Objects.equals(casted.b, b);
        }

        public Pair<A, B> clone() {
            try {
                return (Pair<A, B>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

    }

    static class Hasher {
        private long time = System.nanoTime() + System.currentTimeMillis() * 31L;

        public int shuffle(long z) {
            z += time;
            z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L;
            return (int) (((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
        }

        public int hash(int x) {
            return shuffle(x);
        }

    }

    static interface IntegerEntryIterator {
        boolean hasNext();

        void next();

        int getEntryKey();

        int getEntryValue();

    }

    static interface Int2ToObjectFunction<T> {
        T apply(int a, int b);

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class BlockChain<S, U, E, B extends BlockChain.Block<S, U, E, B>> {
        BlockChain.LinkedNode<B> head = new BlockChain.LinkedNode<>();
        BlockChain.LinkedNode<B> tail = new BlockChain.LinkedNode<>();
        int B;
        int size;

        public BlockChain(int B, Supplier<B> supplier) {
            //add an empty node
            B block = supplier.get();
            BlockChain.LinkedNode<B> node = new BlockChain.LinkedNode<>();
            node.data = block;
            node.size = 0;
            BlockChain.LinkedNode.link(tail.prev, node);
            BlockChain.LinkedNode.link(node, tail);
        }

        public BlockChain(int n, int B, Int2ToObjectFunction<B> supplier) {
            assert n > 0;
            this.B = B;
            size = n;
            BlockChain.LinkedNode.link(head, tail);
            for (int i = 0; i < n; i += B) {
                int l = i;
                int r = i + B - 1;
                r = Math.min(r, n - 1);
                B block = supplier.apply(l, r);
                BlockChain.LinkedNode<B> node = new BlockChain.LinkedNode<>();
                node.data = block;
                node.size = r - l + 1;
                BlockChain.LinkedNode.link(tail.prev, node);
                BlockChain.LinkedNode.link(node, tail);
            }
        }

        void split(BlockChain.LinkedNode<B> node, int n) {
            //split if necessary
            BlockChain.LinkedNode<B> post = new BlockChain.LinkedNode<>();
            Pair<B, B> pair = node.data.split(n);
            BlockChain.LinkedNode.link(post, node.next);
            BlockChain.LinkedNode.link(node, post);
            post.data = pair.b;
            post.size = node.size - n;
            node.data = pair.a;
            node.size = n;
        }

        void mergeNode(BlockChain.LinkedNode<B> a, BlockChain.LinkedNode<B> b) {
            BlockChain.LinkedNode.link(a, b.next);
            a.data = a.data.merge(b.data);
            a.size += b.size;
        }

        void maintain() {
//        maintainCall++;
//        if (maintainCall < 10) {
//            return;
//        }
//        maintainCall = 0;
            for (BlockChain.LinkedNode<B> node = head.next; node != tail; node = node.next) {
                if (node.size >= 2 * B) {
                    split(node, B);
                } else if (node.prev != head && node.size + node.prev.size <= B) {
                    mergeNode(node.prev, node);
                }
            }
        }

        public E get(int index) {
            for (BlockChain.LinkedNode<B> node = head.next; node != tail; node = node.next) {
                if (node.size <= index) {
                    index -= node.size;
                    continue;
                }
                node.data.beforePartialQuery();
                return node.data.get(index);
            }
            throw new IndexOutOfBoundsException();
        }

        public void insert(int index, E e) {
            for (BlockChain.LinkedNode<B> node = head.next; node != tail; node = node.next) {
                if (node.size < index) {
                    index -= node.size;
                    continue;
                }
                node.data.insert(index, e);
                node.size++;
                size++;
                break;
            }
            maintain();
        }

        public void delete(int index) {
            for (BlockChain.LinkedNode<B> node = head.next; node != tail; node = node.next) {
                if (node.size <= index) {
                    index -= node.size;
                    continue;
                }
                node.data.delete(index);
                node.size--;
                size--;

                break;
            }
            maintain();
        }

        public String toString() {
            StringBuilder ans = new StringBuilder("[");
            for (BlockChain.LinkedNode<B> node = head.next; node != tail; node = node.next) {
                ans.append("<").append(node.data).append(">,");
            }
            if (ans.charAt(ans.length() - 1) == ',') {
                ans.setLength(ans.length() - 1);
            }
            ans.append("]");
            return ans.toString();
        }

        public void query(int L, int R, S sum) {
            int offset = 0;
            for (BlockChain.LinkedNode<B> node = head.next; node != tail; node = node.next) {
                int l = offset;
                int r = offset + node.size - 1;
                offset += node.size;
                if (SegmentUtils.enter(L, R, l, r)) {
                    node.data.fullyQuery(sum);
                } else if (SegmentUtils.leave(L, R, l, r)) {
                    continue;
                } else {
                    node.data.beforePartialQuery();
                    for (int i = Math.max(l, L), to = Math.min(r, R); i <= to; i++) {
                        node.data.partialQuery(i - l, sum);
                    }
                }
            }
        }

        public static interface Block<S, U, E, B extends BlockChain.Block<S, U, E, B>> {
            default void insert(int index, E e) {
                throw new UnsupportedOperationException();
            }

            default void delete(int index) {
                throw new UnsupportedOperationException();
            }

            default E get(int index) {
                throw new UnsupportedOperationException();
            }

            Pair<B, B> split(int n);

            B merge(B block);

            void fullyQuery(S sum);

            void partialQuery(int index, S sum);

            default void beforePartialQuery() {

            }

        }

        private static class LinkedNode<E> {
            BlockChain.LinkedNode<E> prev;
            BlockChain.LinkedNode<E> next;
            int size;
            E data;

            static <T> void link(BlockChain.LinkedNode<T> a, BlockChain.LinkedNode<T> b) {
                b.prev = a;
                a.next = b;
            }

            public String toString() {
                return "" + data;
            }

        }

    }

    static class Buffer<T> {
        private Deque<T> deque;
        private Supplier<T> supplier;
        private Consumer<T> cleaner;
        private int allocTime;
        private int releaseTime;

        public Buffer(Supplier<T> supplier) {
            this(supplier, (x) -> {
            });
        }

        public Buffer(Supplier<T> supplier, Consumer<T> cleaner) {
            this(supplier, cleaner, 0);
        }

        public Buffer(Supplier<T> supplier, Consumer<T> cleaner, int exp) {
            this.supplier = supplier;
            this.cleaner = cleaner;
            deque = new ArrayDeque<>(exp);
        }

        public T alloc() {
            allocTime++;
            return deque.isEmpty() ? supplier.get() : deque.removeFirst();
        }

        public void release(T e) {
            releaseTime++;
            cleaner.accept(e);
            deque.addLast(e);
        }

    }

    static class IntegerHashMap {
        private int now;
        private int[] slot;
        private int[] version;
        private int[] next;
        private int[] keys;
        private int[] values;
        private int alloc;
        private boolean[] removed;
        private int mask;
        private int size;
        private boolean rehash;
        private Hasher hasher = new Hasher();

        public IntegerHashMap(int cap, boolean rehash) {
            now = 1;
            this.mask = (1 << (32 - Integer.numberOfLeadingZeros(cap - 1))) - 1;
            slot = new int[mask + 1];
            version = new int[slot.length];
            next = new int[cap + 1];
            keys = new int[cap + 1];
            values = new int[cap + 1];
            removed = new boolean[cap + 1];
            this.rehash = rehash;
        }

        private void doubleCapacity() {
            int newSize = Math.max(next.length + 10, next.length * 2);
            next = Arrays.copyOf(next, newSize);
            keys = Arrays.copyOf(keys, newSize);
            values = Arrays.copyOf(values, newSize);
            removed = Arrays.copyOf(removed, newSize);
        }

        public void alloc() {
            alloc++;
            if (alloc >= next.length) {
                doubleCapacity();
            }
            next[alloc] = 0;
            removed[alloc] = false;
            size++;
        }

        private void rehash() {
            int[] newSlots = new int[Math.max(16, slot.length * 2)];
            int[] newVersions = new int[newSlots.length];
            int newMask = newSlots.length - 1;
            for (int i = 0; i < slot.length; i++) {
                access(i);
                if (slot[i] == 0) {
                    continue;
                }
                int head = slot[i];
                while (head != 0) {
                    int n = next[head];
                    int s = hash(keys[head]) & newMask;
                    next[head] = newSlots[s];
                    newSlots[s] = head;
                    head = n;
                }
            }
            this.slot = newSlots;
            this.version = newVersions;
            now = 0;
            this.mask = newMask;
        }

        private int hash(int x) {
            return hasher.hash(x);
        }

        public void modify(int x, int dy) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                alloc();
                slot[s] = alloc;
                keys[alloc] = x;
                values[alloc] = dy;
            } else {
                int index = findIndexOrLastEntry(s, x);
                if (keys[index] != x) {
                    alloc();
                    next[index] = alloc;
                    keys[alloc] = x;
                    values[alloc] = dy;
                } else {
                    values[index] += dy;
                }
            }
            if (rehash && size >= slot.length) {
                rehash();
            }
        }

        public int getOrDefault(int x, int def) {
            int h = hash(x);
            int s = h & mask;
            access(s);
            if (slot[s] == 0) {
                return def;
            }
            int index = findIndexOrLastEntry(s, x);
            return keys[index] == x ? values[index] : def;
        }

        public int get(int x) {
            return getOrDefault(x, 0);
        }

        private int findIndexOrLastEntry(int s, int x) {
            int iter = slot[s];
            while (keys[iter] != x) {
                if (next[iter] != 0) {
                    iter = next[iter];
                } else {
                    return iter;
                }
            }
            return iter;
        }

        public void clear() {
            alloc = 0;
            size = 0;
            now++;
        }

        private void access(int i) {
            if (version[i] != now) {
                version[i] = now;
                slot[i] = 0;
            }
        }

        public IntegerEntryIterator iterator() {
            return new IntegerEntryIterator() {
                int index = 1;
                int readIndex = -1;


                public boolean hasNext() {
                    while (index <= alloc && removed[index]) {
                        index++;
                    }
                    return index <= alloc;
                }


                public int getEntryKey() {
                    return keys[readIndex];
                }


                public int getEntryValue() {
                    return values[readIndex];
                }


                public void next() {
                    if (!hasNext()) {
                        throw new IllegalStateException();
                    }
                    readIndex = index;
                    index++;
                }
            };
        }

        public String toString() {
            IntegerEntryIterator iterator = iterator();
            StringBuilder builder = new StringBuilder("{");
            while (iterator.hasNext()) {
                iterator.next();
                builder.append(iterator.getEntryKey()).append("->").append(iterator.getEntryValue()).append(',');
            }
            if (builder.charAt(builder.length() - 1) == ',') {
                builder.setLength(builder.length() - 1);
            }
            builder.append('}');
            return builder.toString();
        }

    }

    static class BlockImpl implements BlockChain.Block<Sum, Void, Integer, BlockImpl> {
        static int B = 300;
        static Buffer<BlockImpl> alloc = new Buffer<>(() -> new BlockImpl(), entity -> {
            entity.size = 0;
        });
        IntegerHashMap map = new IntegerHashMap(B * 2, false);
        int[] data = new int[B * 2];
        int size = 0;

        public void insert(int index, Integer integer) {
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = integer;
            size++;
            map.modify(integer, 1);
        }

        public void delete(int index) {
            map.modify(data[index], -1);
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
        }

        public static BlockImpl newInstance(int[] data, int l, int r) {
            BlockImpl ans = alloc.alloc();
            ans.init(data, l, r);
            return ans;
        }

        public void init(int[] data, int l, int r) {
            size = r - l + 1;
            for (int i = l; i <= r; i++) {
                this.data[i - l] = data[i];
            }
            afterPartialUpdate();
        }

        public Pair<BlockImpl, BlockImpl> split(int n) {
            BlockImpl pre = newInstance(data, 0, n - 1);
            BlockImpl post = newInstance(data, n, size - 1);
            alloc.release(this);
            return new Pair<>(pre, post);
        }

        public BlockImpl merge(BlockImpl block) {
            beforePartialQuery();
            block.beforePartialQuery();
            for (int i = 0; i < block.size; i++) {
                data[size++] = block.data[i];
            }
            afterPartialUpdate();
            alloc.release(block);
            return this;
        }

        public void fullyQuery(Sum sum) {
            sum.cnt += map.get(sum.x);
        }

        public void partialQuery(int index, Sum sum) {
            if (data[index] == sum.x) {
                sum.cnt++;
            }
        }

        public void afterPartialUpdate() {
            map.clear();
            for (int i = 0; i < size; i++) {
                map.modify(data[i], 1);
            }
        }

        public String toString() {
            int[] d = Arrays.copyOf(data, size);
            return Arrays.toString(d);
        }

        public void beforePartialQuery() {
        }

        public Integer get(int index) {
            return data[index];
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int[] ri(int n) {
            int[] ans = new int[n];
            populate(ans);
            return ans;
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class Debug {
        private boolean offline;
        private PrintStream out = System.err;
        static int[] empty = new int[0];

        public Debug(boolean enable) {
            offline = enable && System.getSecurityManager() == null;
        }

        public boolean enable() {
            return offline;
        }

        public Debug debug(String name, Object x) {
            return debug(name, x, empty);
        }

        public Debug debug(String name, Object x, int... indexes) {
            if (offline) {
                if (x == null || !x.getClass().isArray()) {
                    out.append(name);
                    for (int i : indexes) {
                        out.printf("[%d]", i);
                    }
                    out.append("=").append("" + x);
                    out.println();
                } else {
                    indexes = Arrays.copyOf(indexes, indexes.length + 1);
                    if (x instanceof byte[]) {
                        byte[] arr = (byte[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof short[]) {
                        short[] arr = (short[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof boolean[]) {
                        boolean[] arr = (boolean[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof char[]) {
                        char[] arr = (char[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof int[]) {
                        int[] arr = (int[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof float[]) {
                        float[] arr = (float[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof double[]) {
                        double[] arr = (double[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else if (x instanceof long[]) {
                        long[] arr = (long[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    } else {
                        Object[] arr = (Object[]) x;
                        for (int i = 0; i < arr.length; i++) {
                            indexes[indexes.length - 1] = i;
                            debug(name, arr[i], indexes);
                        }
                    }
                }
            }
            return this;
        }

    }

    static class SegmentUtils {
        public static boolean enter(int L, int R, int l, int r) {
            return L <= l && R >= r;
        }

        public static boolean leave(int L, int R, int l, int r) {
            return L > r || R < l;
        }

    }
}