You are given an array $a$, consisting of $n$ integers. Your task is to process $q$ queries of two types:

• $1~p~x$ — set the value of the element at index $p$ equal to $x$;
• $2~l~r$ — count the number of pairs of indices $(i, j)$ such that $l \le i < j \le r$ and $a_i \ne a_j$.

Note that the queries in this task are encoded; each subsequent query can only be decoded after calculating the answer to the preceding query of the second type.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

The third line contains a single integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The next $q$ lines describe the queries in one of the following formats:

• $1~p'~x'$ ($0 \le p', x' \le n-1$);
• $2~l'~r'$ ($0 \le l', r' \le n-1$).

The queries are encoded as follows: let $\mathit{last}$ be the answer to the latest processed query of the second type (initially, $\mathit{last} = 0$).

• if the type of the query is $1$, then $p = ((p' + \mathit{last}) \bmod n) + 1$, $x = ((x' + \mathit{last}) \bmod n) + 1$.
• if the type of the query is $2$, $l = ((l' + \mathit{last}) \bmod n) + 1$, $r = ((r' + \mathit{last}) \bmod n) + 1$. If $l > r$, swap their values.

Don't forget to update the value of $\mathit{last}$ after answering each query of the second type.

Additional constraint on the input: there is at least one query of the second type.

Output

For each query of the second type, print the answer — the number of pairs of indices $(i, j)$ such that $l \le i < j \le r$ and $a_i \ne a_j$.

见题面 Input 部分

见题面 Output 部分

In the first example, the actual queries (after decoding) are:

• 2 1 3
• 1 1 3
• 2 1 3
• 1 2 3
• 2 1 3