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;
template <class T>
inline void umax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void umin(T &a, T b) {
  if (a > b) a = b;
}
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <class T>
inline T gcd(T a, T b) {
  return __gcd(a, b);
}
template <class T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
const int inf = 1e9 + 143;
const long long longinf = 1e18 + 143;
inline int read() {
  int x;
  scanf(" %d", &x);
  return x;
}
const int N = int(1e5) + 100;
const int K = 700;
const int NK = N / K + 10;
int a[N];
int big_id[N], ptr = 0;
vector<int> loc[N];
struct node {
  node *l, *r;
  int *cnt;
  int x, y, sz;
  node(int _x = 0);
};
node *null;
node::node(int _x) {
  x = _x;
  y = rand() << 16 ^ rand();
  cnt = new int[NK];
  for (int i = 0; i < NK; i++) cnt[i] = 0;
  if (big_id[x] != -1) cnt[big_id[x]] = 1;
  sz = 1;
  l = r = null;
}
inline void relax(node *p) {
  p->sz = 1 + p->l->sz + p->r->sz;
  for (int i = 0; i < NK; i++) p->cnt[i] = p->l->cnt[i] + p->r->cnt[i];
  if (big_id[p->x] != -1) p->cnt[big_id[p->x]]++;
}
node *merge(node *l, node *r) {
  if (l == null) return r;
  if (r == null) return l;
  if (l->y > r->y) {
    l->r = merge(l->r, r);
    relax(l);
    return l;
  } else {
    r->l = merge(l, r->l);
    relax(r);
    return r;
  }
}
void split(node *root, node *&l, node *&r, int from) {
  if (root == null) {
    l = r = null;
    return;
  }
  if (from <= root->l->sz) {
    split(root->l, l, r, from);
    root->l = r;
    relax(root);
    r = root;
  } else {
    split(root->r, l, r, from - root->l->sz - 1);
    root->r = l;
    relax(root);
    l = root;
  }
}
node *rotate1(node *root, int x1, int x2) {
  node *l, *m, *r;
  split(root, l, r, x1 - 1);
  split(r, m, r, x2 - x1 + 1);
  {
    node *T1, *T2;
    split(m, T1, T2, x2 - x1);
    m = merge(T2, T1);
  }
  return merge(l, merge(m, r));
}
int get_ans(node *&root, int x1, int x2, int k) {
  node *l, *m, *r;
  split(root, l, r, x1 - 1);
  split(r, m, r, x2 - x1 + 1);
  int t = m->cnt[big_id[k]];
  root = merge(l, merge(m, r));
  return t;
}
namespace TA2 {
struct treap {
  treap *l, *r, *par;
  int x, y, sz;
  treap(int _x = 0);
};
treap *null2;
treap *pos[N];
treap::treap(int _x) {
  x = _x;
  y = rand() << 16 ^ rand();
  sz = 1;
  l = r = par = null2;
}
inline void relax(treap *&p) {
  p->sz = 1 + p->l->sz + p->r->sz;
  if (p->l != null2) p->l->par = p;
  if (p->r != null2) p->r->par = p;
}
treap *merge(treap *l, treap *r) {
  if (l == null2) return r;
  if (r == null2) return l;
  if (l->y > r->y) {
    l->r = merge(l->r, r);
    relax(l);
    return l;
  } else {
    r->l = merge(l, r->l);
    relax(r);
    return r;
  }
}
void split(treap *root, treap *&l, treap *&r, int from) {
  if (root == null2) {
    l = r = null2;
    return;
  }
  if (from <= root->l->sz) {
    split(root->l, l, r, from);
    root->l = r;
    relax(root);
    r = root;
  } else {
    split(root->r, l, r, from - root->l->sz - 1);
    root->r = l;
    relax(root);
    l = root;
  }
}
treap *rotate2(treap *root, int x1, int x2) {
  treap *l, *m, *r;
  split(root, l, r, x1 - 1);
  split(r, m, r, x2 - x1 + 1);
  {
    treap *T1, *T2;
    split(m, T1, T2, x2 - x1);
    m = merge(T2, T1);
  }
  return merge(l, merge(m, r));
}
inline int get_pos(treap *&root, int x) {
  treap *p = pos[x];
  int ans = p->l->sz;
  while (p != root) {
    treap *next = p->par;
    if (next->r == p) ans += next->l->sz + 1;
    assert(next->l == p || next->r == p);
    p = next;
  }
  return ans + 1;
}
int get_ans2(treap *&root, int x1, int x2, int k) {
  int ans = 0;
  for (__typeof((loc[k]).begin()) it = (loc[k]).begin(); it != (loc[k]).end();
       it++) {
    int x = *it;
    int y = get_pos(root, x);
    if (y <= x2 && y >= x1) ++ans;
  }
  return ans;
}
};  // namespace TA2
int main() {
  srand(time(0));
  null = new node();
  null->sz = 0;
  null->x = null->y = 0;
  null->cnt = new int[NK];
  for (int i = 0; i < NK; i++) null->cnt[i] = 0;
  null->l = null->r = null;
  TA2::null2 = new TA2::treap();
  TA2::null2->sz = TA2::null2->x = TA2::null2->y = 0;
  TA2::null2->l = TA2::null2->r = TA2::null2->par = TA2::null2;
  int n = read();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    loc[a[i]].push_back(i);
  }
  for (int i = 0; i < N; i++) {
    if (loc[i].size() > K) {
      big_id[i] = ptr++;
    } else {
      big_id[i] = -1;
    }
  }
  node *root = null;
  TA2::treap *root2 = TA2::null2;
  for (int i = 1; i <= n; i++) {
    root = merge(root, new node(a[i]));
    TA2::pos[i] = new TA2::treap(a[i]);
    root2 = TA2::merge(root2, TA2::pos[i]);
  }
  int q = read();
  int lastans = 0;
  for (int i = 0; i < q; i++) {
    int t = read();
    if (t == 1) {
      int l = read(), r = read();
      l = (l + lastans - 1) % n + 1;
      r = (r + lastans - 1) % n + 1;
      if (l > r) swap(l, r);
      root = rotate1(root, l, r);
      root2 = TA2::rotate2(root2, l, r);
    } else {
      int l = read(), r = read(), k = read();
      l = (l + lastans - 1) % n + 1;
      r = (r + lastans - 1) % n + 1;
      k = (k + lastans - 1) % n + 1;
      if (l > r) swap(l, r);
      if (big_id[k] != -1) {
        lastans = get_ans(root, l, r, k);
      } else {
        lastans = TA2::get_ans2(root2, l, r, k);
      }
      printf("%d\n", lastans);
    }
  }
  return 0;
}