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 Get() {
  int res = 0, q = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') q = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
  return res * q;
}
const double eps = 1e-12, pi = M_PI;
const int oo = (int)2e9, mod = (int)1e9 + 7;
const long long INF = (long long)1e17;
const int N = (int)1e5, E = 318;
typedef int arr[N + 10];
arr nex, par, key;
int ed[E + 1], pd[E + 1];
int c[E + 1][N + 1];
int n, m, S, block, ans;
void Prepare() {
  ((n) = Get()), S = (int)sqrt(n), block = 1;
  for (int i = (1), end = (n); i <= end; ++i) {
    nex[i] = i + 1, par[i] = i - 1, ((key[i]) = Get());
    ++c[block][key[i]];
    if (i % S == 0) pd[block] = i, ed[block++] = i;
  }
  if (n % S)
    ed[block] = pd[block] = n;
  else
    --block;
  nex[0] = 1, par[n + 1] = n;
}
int Find(int x, int y) {
  int now = nex[ed[x - 1]], cnt = pd[x - 1] + 1;
  for (; cnt != y; now = nex[now], ++cnt)
    ;
  return now;
}
void Modify(int x, int y) {
  int sx = (x - 1) / S + 1, sy = (y - 1) / S + 1;
  if (x == y) return;
  x = Find(sx, x), y = Find(sy, y);
  if (ed[sy] == y) ed[sy] = par[y];
  nex[par[y]] = nex[y], par[nex[y]] = par[y];
  nex[par[x]] = y, par[y] = par[x];
  nex[y] = x, par[x] = y;
  --c[sy][key[y]], ++c[sx][key[y]];
  for (int i = (sx), end = (sy - 1); i <= end; ++i) {
    --c[i][key[ed[i]]], ++c[i + 1][key[ed[i]]];
    ed[i] = par[ed[i]];
  }
}
int Query(int x, int y, int z) {
  int sx = (x - 1) / S + 1, sy = (y - 1) / S + 1, res = 0;
  if (sx == sy) {
    int now = nex[ed[sx - 1]], cnt = pd[sx - 1] + 1;
    for (; cnt != x; now = nex[now], ++cnt)
      ;
    for (; cnt <= y; now = nex[now], ++cnt) res += (key[now] == z);
    return res;
  }
  for (int i = (sx + 1), end = (sy - 1); i <= end; ++i) res += c[i][z];
  int now = ed[sx], cnt = pd[sx];
  for (; cnt >= x; now = par[now], --cnt) res += (key[now] == z);
  now = nex[ed[sy - 1]], cnt = pd[sy - 1] + 1;
  for (; cnt <= y; now = nex[now], ++cnt) res += (key[now] == z);
  return res;
}
void Calc() {
  int tp, j, k, p;
  ((m) = Get());
  for (int o = (1), end = (m); o <= end; ++o) {
    ((tp) = Get());
    if (tp == 1) {
      ((j) = Get()), ((k) = Get());
      j = (j + ans - 1) % n + 1, k = (k + ans - 1) % n + 1;
      if (j > k) swap(j, k);
      Modify(j, k);
    } else {
      ((j) = Get()), ((k) = Get()), ((p) = Get());
      j = (j + ans - 1) % n + 1, k = (k + ans - 1) % n + 1,
      p = (p + ans - 1) % n + 1;
      if (j > k) swap(j, k);
      printf(
          "%d"
          "\n",
          ans = Query(j, k, p));
    }
  }
}
int main() {
  Prepare();
  Calc();
  return 0;
}