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;
inline int Read() {
  char c = getchar();
  int nm = 0;
  while ('0' > c || c > '9') c = getchar();
  while ('0' <= c && c <= '9') nm = nm * 10 + c - '0', c = getchar();
  return (nm);
}
int wr[10], wt;
inline void Write(int x) {
  if (!x) {
    puts("0");
    return;
  }
  for (wt = 0; x; x /= 10) wr[++wt] = x % 10;
  for (int i = wt; i; i--) putchar((char)wr[i] + '0');
  puts("");
}
int n, m, ans, bl[100010], w[350][100010], s, a[100010];
int b[350][1510], R[350], L[350], sz[350], st[350], cnt, bk;
inline int Get(int x) { return (((x + ans - 1) % n) + 1); }
int main() {
  n = Read();
  bk = min(300, (int)(sqrt((double)n + m) + .5)), s = (n - bk + 1) / bk;
  for (int i = 1; i <= n; i++) a[i] = Read();
  for (int i = 1; i <= n; i += s) {
    cnt++, st[cnt] = 1000 + 1, sz[cnt] = 1000;
    L[cnt] = i, R[cnt] = min(n, i + s - 1);
    for (int j = i; j <= R[cnt]; j++) {
      b[cnt][++sz[cnt]] = a[j];
      w[cnt][a[j]]++, bl[j] = cnt;
    }
  }
  m = Read();
  for (int i = 1; i <= m; i++) {
    int op = Read(), l, r, k;
    if (op == 1) {
      l = Read(), r = Read();
      l = Get(l), r = Get(r);
      if (l > r) swap(l, r);
      int pl = bl[l], pr = bl[r];
      int al = b[pl][sz[pl]], ar = b[pr - 1][sz[pr - 1]];
      int hd = b[pl][st[pl] + l - L[pl]], ed = b[pr][st[pr] + r - L[pr]];
      if (pl == pr) {
        int sp = st[pl], h = b[pl][sp + l - L[pl]];
        for (int j = r; j > l; j--)
          b[pl][sp + j - L[pl]] = b[pl][sp + j - L[pl] - 1];
        b[pl][sp + l - L[pl]] = ed;
        continue;
      }
      for (int j = pr - 1; j > pl; j--) {
        int ad = b[j - 1][sz[j - 1]];
        w[j][b[j][sz[j]]]--, sz[j]--;
        b[j][--st[j]] = ad, w[j][ad]++;
      }
      for (int j = r; j > L[pr]; j--)
        b[pr][st[pr] + j - L[pr]] = b[pr][st[pr] + j - L[pr] - 1];
      b[pr][st[pr]] = ar, w[pr][ar]++, w[pr][ed]--;
      for (int j = R[pl]; j > l; j--)
        b[pl][st[pl] + j - L[pl]] = b[pl][st[pl] + j - L[pl] - 1];
      b[pl][st[pl] + l - L[pl]] = ed, w[pl][ed]++, w[pl][al]--;
      for (int j = pl + 1; j < pr; j++) {
        if (st[j] > 1) continue;
        for (int k = st[j]; k <= sz[j]; k++) b[j][k + 1000] = b[j][k];
        sz[j] += 1000, st[j] += 1000;
      }
    } else {
      l = Read(), r = Read(), k = Read();
      l = Get(l), r = Get(r), k = Get(k);
      if (l > r) swap(l, r);
      ans = 0;
      int pl = bl[l], pr = bl[r];
      if (pl == pr) {
        for (int j = l; j <= r; j++)
          if (b[pl][st[pl] + j - L[pl]] == k) ans++;
        Write(ans);
        continue;
      }
      for (int j = pl + 1; j < pr; j++) ans += w[j][k];
      for (int j = l; j <= R[pl]; j++)
        if (b[pl][st[pl] + j - L[pl]] == k) ans++;
      for (int j = L[pr]; j <= r; j++)
        if (b[pr][st[pr] + j - L[pr]] == k) ans++;
      Write(ans);
    }
  }
}