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;
int qreadInt() {
  int x = 0, op = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') op = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') (x *= 10) += (ch - '0'), ch = getchar();
  return x * op;
}
void cmin(int &x, int y) { x = (x > y) ? y : x; }
void cmax(int &x, int y) { x = (x < y) ? y : x; }
int n, m, szn, szm, tot;
int w[444][1500], sum[444][100010], lf[444], rt[444], bl[200010], s[200010],
    num[200010];
void build(int p) {
  for (int i = 1; i <= n; i += szn) {
    for (int j = 1; j <= szn; ++j) {
      w[bl[i]][j + szn] = s[i - 1 + j];
      if (p) sum[bl[i]][s[i - 1 + j]]++;
    }
    lf[bl[i]] = szn + 1, rt[bl[i]] = szn + szn;
  }
}
void rebuild() {
  for (int i = 1; i <= n; i += szn)
    for (int j = 1; j <= szn; ++j) s[i - 1 + j] = w[bl[i]][lf[bl[i]] + j - 1];
  build(0);
}
signed main() {
  n = qreadInt();
  for (int i = (1); i <= (n); ++i) s[i] = qreadInt();
  szn = sqrt(n), szm = szn, tot = 0;
  int pt = 1, temp = 0;
  for (int i = (1); i <= (n); ++i) {
    temp++;
    bl[i] = pt, num[i] = temp;
    if (temp == szn) temp = 0, pt++;
  }
  build(1);
  int la = 0;
  m = qreadInt();
  while (m--) {
    if (tot == szm) rebuild(), tot = 0;
    tot++;
    int op = qreadInt();
    if (op == 1) {
      int l = qreadInt(), r = qreadInt();
      l = ((l + la - 1) % n) + 1, r = ((r + la - 1) % n) + 1;
      if (l > r) swap(l, r);
      int bll = bl[l], blr = bl[r];
      if (bll != blr) {
        int tmp = w[bll][rt[bll]];
        sum[bll][tmp]--;
        for (int i = (rt[bll]); i >= (lf[bll] + num[l]); --i)
          w[bll][i] = w[bll][i - 1];
        w[bll][lf[bll] + num[l] - 1] = w[blr][lf[blr] + num[r] - 1];
        sum[bll][w[bll][lf[bll] + num[l] - 1]]++;
        for (int i = (bll + 1); i <= (blr - 1); ++i) {
          sum[i][tmp]++;
          w[i][lf[i] - 1] = tmp;
          tmp = w[i][rt[i]];
          sum[i][tmp]--;
          lf[i]--, rt[i]--;
        }
        sum[blr][w[blr][lf[blr] + num[r] - 1]]--;
        for (int i = (lf[blr] + num[r] - 1); i >= (lf[blr] + 1); --i)
          w[blr][i] = w[blr][i - 1];
        w[blr][lf[blr]] = tmp;
        sum[blr][tmp]++;
      } else {
        int tmp = w[blr][lf[blr] + num[r] - 1];
        for (int i = (lf[blr] + num[r] - 1); i >= (lf[bll] + num[l]); --i)
          w[blr][i] = w[bll][i - 1];
        w[bll][lf[bll] + num[l] - 1] = tmp;
      }
    } else {
      int l = qreadInt(), r = qreadInt(), k = qreadInt();
      l = ((l + la - 1) % n) + 1, r = ((r + la - 1) % n) + 1,
      k = ((k + la - 1) % n) + 1;
      if (l > r) swap(l, r);
      int bll = bl[l], blr = bl[r], Ans = 0;
      if (bll != blr) {
        for (int i = (lf[bll] + num[l] - 1); i <= (rt[bll]); ++i)
          Ans += ((w[bll][i] == k) ? 1 : 0);
        for (int i = (bll + 1); i <= (blr - 1); ++i) Ans += sum[i][k];
        for (int i = (lf[blr]); i <= (lf[blr] + num[r] - 1); ++i)
          Ans += ((w[blr][i] == k) ? 1 : 0);
      } else {
        for (int i = (lf[bll] + num[l] - 1); i <= (lf[bll] + num[r] - 1); ++i)
          Ans += ((w[bll][i] == k) ? 1 : 0);
      }
      printf("%d\n", Ans);
      la = Ans;
    }
  }
  return 0;
}