CF455D.Serega and Fun

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?

谢尔加喜欢有趣的事情。然而，每个人享受乐趣的方式都各不相同。谢尔加的乐趣在于解决查询类问题。有一天，费奥多尔提出了这样一个问题。

给你一个由 $n$ 个正整数组成的数组 $a$，以及对该数组的一系列查询。查询分为两种类型：

1. 对区间 $[l, r]$（两端均包含）执行一次向右的循环移位（即单位循环右移）。也就是说，将该区间内的数组元素按如下方式重新排列：
   $a[l],\ a[l + 1],\ \dots,\ a[r - 1],\ a[r]\ \to\ a[r],\ a[l],\ a[l + 1],\ \dots,\ a[r - 1]$。

2. 统计区间 $[l, r]$（两端均包含）内等于 $k$ 的数的个数。

费奥多尔迫不及待地想看到谢尔加享受这道题，而谢尔加也迅速地解决了它。那么，你能否也解出来呢？

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:

l__i = ((l'i + lastans - 1) mod n) + 1; r__i = ((r'i + lastans - 1) mod n) + 1; k__i = ((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 l__i is greater than r__i, you must swap these values.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 表示数组的元素个数。
第二行包含 $n$ 个整数 $a[1],\ a[2],\ \dots,\ a[n]$（$1 \leq a[i] \leq n$）。

第三行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 表示查询的个数。接下来的 $q$ 行为查询内容。

由于你需要在线回答这些查询，因此输入中的查询是经过编码的。第一类查询的格式为：1 l'_i r'_i；第二类查询的格式为：2 l'_i r'_i k'_i。输入中所有数字均为整数，且满足约束：$1 \leq l'_i,\ r'_i,\ k'_i \leq n$。

为从输入数据中解码查询，需执行如下变换：

$$l_i = ((l'_i + \text{lastans} - 1) \bmod n) + 1;\quad r_i = ((r'_i + \text{lastans} - 1) \bmod n) + 1;\quad k_i = ((k'_i + \text{lastans} - 1) \bmod n) + 1.$$

其中 $\text{lastans}$ 表示上一次第二类查询的答复（初始时 $\text{lastans} = 0$）。若变换后 $l_i > r_i$，则必须交换 $l_i$ 与 $r_i$ 的值。

For each query of the 2-nd type print the answer on a single line.

对于每个第 2 类查询，在单独一行输出答案。