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;
struct Node;
int n, m;
vector<int> a;
vector<Node *> rt;
vector<queue<Node *> > q;
Node *empty, *lsen, *rsen;
struct Node {
  int val, siz;
  Node *pa, *mir;
  vector<Node *> ch;
  Node(Node *_pa = empty, int _val = 0, Node *_mir = empty) {
    siz = 1;
    pa = _pa;
    mir = _mir;
    val = _val;
    ch.resize(2, empty);
  }
};
void pushup(Node *x) { x->siz = x->ch[0]->siz + x->ch[1]->siz + 1; }
void rotate(Node *x) {
  Node *y = x->pa;
  Node *z = y->pa;
  int k = x == y->ch[1];
  z->ch[y == z->ch[1]] = x;
  x->pa = z;
  y->ch[k] = x->ch[k ^ 1];
  x->ch[k ^ 1]->pa = y;
  x->ch[k ^ 1] = y;
  y->pa = x;
  pushup(y);
  pushup(x);
}
void Splay(Node *x, Node *goal) {
  while (x->pa != goal) {
    Node *y = x->pa;
    Node *z = y->pa;
    if (z != goal) rotate((x == y->ch[1]) ^ (y == z->ch[1]) ? x : y);
    rotate(x);
  }
}
void makeroot(Node *&root, Node *x) {
  Splay(x, empty);
  root = x;
}
Node *kth(Node *root, int x) {
  Node *u = root;
  while (1) {
    if (u->ch[0]->siz >= x)
      u = u->ch[0];
    else if (u->ch[0]->siz + 1 == x)
      return u;
    else {
      x -= u->ch[0]->siz + 1;
      u = u->ch[1];
    }
  }
}
int rk(Node *&root, Node *x) {
  makeroot(root, x);
  return x->ch[0]->siz + 1;
}
void link(Node *&root, Node *x, Node *y, int type = 0) {
  makeroot(root, y);
  if (root->ch[type] != empty) {
    Node *u = kth(y->ch[0], y->ch[0]->siz);
    makeroot(root, u);
  }
  y->ch[type] = x;
  x->pa = y;
  pushup(y);
  if (y->pa != empty) pushup(y->pa);
}
void cut(Node *&root, Node *x) {
  makeroot(root, x);
  Node *u = kth(x->ch[0], x->ch[0]->siz);
  makeroot(root, u);
  u->ch[1] = x->ch[1];
  x->ch[1]->pa = u;
  x->ch[0] = x->ch[1] = x->pa = empty;
  x->siz = 1;
  pushup(u);
}
Node *rkle(Node *root, int x) {
  Node *u = root;
  while (1) {
    if (u->ch[1] != empty && rk(rt[0], kth(u->ch[1], 1)->mir) <= x)
      u = u->ch[1];
    else if (rk(rt[0], u->mir) <= x)
      return u;
    else
      u = u->ch[0];
  }
}
Node *rkge(Node *root, int x) {
  Node *u = root;
  while (1) {
    if (u->ch[0] != empty && rk(rt[0], kth(u->ch[0], u->ch[0]->siz)->mir) >= x)
      u = u->ch[0];
    else if (rk(rt[0], u->mir) >= x)
      return u;
    else
      u = u->ch[1];
  }
}
Node *split(Node *&root, int l, int r) {
  Node *x = kth(root, l);
  Node *y = kth(root, r + 2);
  makeroot(root, x);
  Splay(y, x);
  return y->ch[0];
}
Node *get(Node *&root, int p) {
  Node *x = rkle(root, p);
  Node *y = rkge(root, p + 2);
  makeroot(root, x);
  Splay(y, x);
  return y->ch[0];
}
Node *build1(vector<int>::iterator l, vector<int>::iterator r, Node *pa) {
  if (l == r) return empty;
  auto mid = l + (r - l) / 2;
  Node *cur = new Node(pa, *mid);
  cur->ch[0] = build1(l, mid, cur);
  q[*mid].push(cur);
  cur->ch[1] = build1(mid + 1, r, cur);
  pushup(cur);
  return cur;
}
void build1(Node *&root, vector<int> &a) {
  root = build1(a.begin(), a.end(), empty);
  lsen = new Node();
  link(root, lsen, kth(root, 1));
  rsen = new Node();
  link(root, rsen, kth(root, root->siz), 1);
}
Node *build2(int l, int r, int val, Node *pa) {
  if (l == r) return empty;
  int mid = (l + r) >> 1;
  Node *cur = new Node(pa, val);
  cur->ch[0] = build2(l, mid, val, cur);
  cur->mir = q[val].front();
  q[val].pop();
  cur->ch[1] = build2(mid + 1, r, val, cur);
  pushup(cur);
  return cur;
}
void build2(Node *&root, int size, int val) {
  if (size == 0) return;
  root = build2(0, size, val, empty);
  Node *lsentry = new Node(empty, 0, lsen);
  link(root, lsentry, kth(root, 1));
  Node *rsentry = new Node(empty, 0, rsen);
  link(root, rsentry, kth(root, root->siz), 1);
}
int main() {
  empty = new Node();
  empty->siz = 0;
  empty->ch[0] = empty->ch[1] = empty->pa = empty->mir = empty;
  scanf("%d", &n);
  a.resize(n, 0);
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  rt.resize(n + 1);
  q.resize(n + 1);
  build1(rt[0], a);
  for (int i = 1; i <= n; ++i) build2(rt[i], q[i].size(), i);
  scanf("%d", &m);
  int ans = 0;
  while (m--) {
    int type, l, r;
    scanf("%d%d%d", &type, &l, &r);
    l = (l + ans - 1) % n + 1;
    r = (r + ans - 1) % n + 1;
    if (l > r) swap(l, r);
    if (type == 1) {
      if (l == r) continue;
      Node *x = split(rt[0], l, r);
      Node *y = kth(x, 1);
      Node *z = kth(x, x->siz);
      int k = z->val;
      x = get(rt[k], r);
      cut(rt[k], x);
      Node *qaq = rkle(rt[k], l);
      Node *qwq = rkge(rt[k], l + 1);
      makeroot(rt[k], qaq);
      Splay(qwq, qaq);
      link(rt[k], x, qwq);
      cut(rt[0], z);
      link(rt[0], z, y);
    } else {
      int k;
      scanf("%d", &k);
      k = (k + ans - 1) % n + 1;
      if (rt[k] == 0) {
        ans = 0;
        puts("0");
        continue;
      }
      Node *x = rkle(rt[k], l);
      Node *y = rkge(rt[k], r + 2);
      makeroot(rt[k], x);
      Splay(y, x);
      ans = y->ch[0]->siz;
      printf("%d\n", ans);
    }
  }
  return 0;
}