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* ≤ 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.

Output

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