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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const double alpha = 0.8;
struct Node {
  int size, key, nodeCount;
  bool isExist;
  Node *lc, *rc;
  map<int, int> mp;
  bool isBad() {
    return lc->nodeCount > alpha * nodeCount + 5 ||
           rc->nodeCount > alpha * nodeCount + 5;
  }
  void merge() {
    size = isExist;
    size += lc->size;
    size += rc->size;
    nodeCount = 1;
    nodeCount += lc->nodeCount;
    nodeCount += rc->nodeCount;
    mp.clear();
    for (auto e : lc->mp) {
      mp[e.first] += e.second;
    }
    for (auto e : rc->mp) {
      mp[e.first] += e.second;
    }
    if (isExist) mp[key]++;
  }
} pool[N * 2], *C = pool + 1, *root, *null;
Node *newNode(int key) {
  C->size = 1;
  C->key = key;
  C->mp.clear();
  C->mp[key] = 1;
  C->isExist = 1;
  C->lc = C->rc = null;
  return C++;
}
int n, q;
Node *buildTree(int *a, int l, int r) {
  if (l >= r) return null;
  int mid = (l + r) / 2;
  Node *p = newNode(a[mid]);
  p->lc = buildTree(a, l, mid);
  p->rc = buildTree(a, mid + 1, r);
  p->merge();
  return p;
}
void dfs(Node *p, vector<Node *> &v) {
  if (p == null) return;
  dfs(p->lc, v);
  v.push_back(p);
  dfs(p->rc, v);
}
Node *divide(vector<Node *> &v, int l, int r) {
  if (l >= r) return null;
  int mid = (l + r) / 2;
  Node *p = v[mid];
  p->lc = divide(v, l, mid);
  p->rc = divide(v, mid + 1, r);
  p->merge();
  return p;
}
void rebuild(Node *&p) {
  vector<Node *> v;
  dfs(p, v);
  p = divide(v, 0, v.size());
}
int erase(Node *p, int idx) {
  if (p->isExist && idx == p->lc->size + 1) {
    p->isExist = 0;
    p->mp[p->key]--;
    p->size--;
    return p->key;
  }
  int res;
  p->size--;
  res = idx <= p->lc->size ? erase(p->lc, idx)
                           : erase(p->rc, idx - p->lc->size - p->isExist);
  p->mp[res]--;
  return res;
}
Node **insert(Node *&p, int idx, int val) {
  if (p == null) {
    p = newNode(val);
    return &null;
  } else {
    p->nodeCount++;
    p->size++;
    p->mp[val]++;
    Node **res = idx <= p->lc->size + 1
                     ? insert(p->lc, idx, val)
                     : insert(p->rc, idx - p->lc->size - p->isExist, val);
    if (p->isBad()) res = &p;
    return res;
  }
}
int getNumber(Node *p, int l, int r, int w) {
  if (p == null) return 0;
  if (l <= 1 && p->size <= r) {
    return p->mp.count(w) ? p->mp[w] : 0;
  } else {
    int res = 0;
    if (l <= p->lc->size) res += getNumber(p->lc, l, r, w);
    if (r > p->lc->size + p->isExist)
      res += getNumber(p->rc, l - p->lc->size - p->isExist,
                       r - p->lc->size - p->isExist, w);
    if (p->isExist && l <= p->lc->size + 1 && p->lc->size + 1 <= r &&
        p->key == w) {
      res++;
    }
    return res;
  }
}
int main() {
  null = pool;
  null->size = 0;
  null->nodeCount = 0;
  null->key = 0;
  null->mp.clear();
  null->isExist = 0;
  null->lc = null->rc = null;
  static int a[N];
  int lastans = 0;
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); i++) {
    scanf("%d", &a[i]);
  }
  root = buildTree(a, 0, n);
  scanf("%d", &q);
  for (int i = 0; i < (int)(q); i++) {
    int op, l, r, w;
    scanf("%d%d%d", &op, &l, &r);
    l = (l + lastans - 1 + n) % n + 1;
    r = (r + lastans - 1 + n) % n + 1;
    if (l > r) swap(l, r);
    if (op == 1) {
      int value = erase(root, r);
      Node **p = insert(root, l, value);
      if (*p != null) rebuild(*p);
    } else if (op == 2) {
      scanf("%d", &w);
      w = (w + lastans - 1 + n) % n + 1;
      lastans = getNumber(root, l, r, w);
      printf("%d\n", lastans);
    }
  }
  return 0;
}