455_D. Serega and Fun_18697
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
#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  for (x = c - '0'; (c = getchar()) >= '0' && c <= '9';) x = x * 10 + c - '0';
  return x;
}
int a[100000 + 5], L[250 + 5], R[250 + 5], qn;
int rt[100000 + 5], u[100000 + 5], l[200000 + 5], r[200000 + 5], w[200000 + 5],
    s[200000 + 5], mk[200000 + 5], q[200000 + 5], z[100000 + 5], zn;
vector<pair<int, int> > v[100000 + 5];
inline int ran() {
  static int x = 23333;
  return x ^= x << 13, x ^= x >> 17, x ^= x << 5;
}
inline void up(int x) { s[x] = s[l[x]] + s[r[x]] + 1; }
inline void add(int x, int z) {
  w[x] += z;
  mk[x] += z;
}
inline void down(int x) {
  if (mk[x]) add(l[x], mk[x]), add(r[x], mk[x]), mk[x] = 0;
}
int merge(int a, int b) {
  if (!a || !b) return a + b;
  if (q[a] > q[b])
    return down(a), r[a] = merge(r[a], b), up(a), a;
  else
    return down(b), l[b] = merge(a, l[b]), up(b), b;
}
void split(int x, int k, int& a, int& b) {
  if (!x) {
    a = b = 0;
    return;
  }
  down(x);
  if (w[x] <= k)
    a = x, split(r[x], k, r[x], b);
  else
    b = x, split(l[x], k, a, l[x]);
  up(x);
}
void build(int x) {
  rt[x] = 0;
  for (int i = 0; i < v[x].size(); ++i) {
    int p = v[x][i].first;
    q[p] = ran();
    r[p] = mk[p] = 0;
    w[p] = v[x][i].second;
    s[p] = 1;
    for (z[zn + 1] = 0; zn && q[p] > q[z[zn]];) up(z[zn--]);
    l[p] = z[zn + 1];
    if (zn)
      r[z[zn]] = p;
    else
      rt[x] = p;
    z[++zn] = p;
  }
  while (zn) up(z[zn--]);
  v[x].clear();
}
void shift(int x, int l, int r) {
  int a, b, c, d;
  split(rt[x], r, a, b);
  split(a, l - 1, a, c);
  split(c, r - 1, c, d);
  add(c, 1);
  w[d] = l;
  rt[x] = merge(merge(a, d), merge(c, b));
}
void dfs(int x) {
  down(x);
  if (l[x]) dfs(l[x]);
  v[a[x]].push_back(make_pair(x + 100000, w[x]));
  if (r[x]) dfs(r[x]);
}
int main() {
  int n = read(), q, i, t, l, r, k, ls = 0;
  for (i = 1; i <= n; ++i)
    v[0].push_back(make_pair(i, i)),
        v[a[i] = read()].push_back(make_pair(i + 100000, i));
  for (i = 0; i <= n; ++i) build(i);
  for (q = read(); q--;) {
    t = read();
    l = (read() + ls - 1) % n + 1;
    r = (read() + ls - 1) % n + 1;
    if (l > r) swap(l, r);
    if (t == 1) {
      L[++qn] = l;
      R[qn] = r;
      shift(0, l, r);
      if (qn == 250) {
        dfs(rt[0]);
        memset(u, qn = 0, sizeof(u));
        for (i = 1; i <= n; ++i) build(i);
      }
    } else {
      k = (read() + ls - 1) % n + 1;
      while (u[k] < qn) ++u[k], shift(k, L[u[k]], R[u[k]]);
      int a, b, c;
      split(rt[k], r, a, b);
      split(a, l - 1, a, c);
      printf("%d\n", ls = s[c]);
      rt[k] = merge(merge(a, c), b);
    }
  }
}
