A9660 | 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?

The first line contains integer $n$ ( $1<=n<=10^{5}$ ) — 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<=10^{5}$ ) — 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.

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