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 \lt 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 \gt 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 \lt j \le r$$$ and $$$a_i \ne a_j$$$.

Note

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

Problem with Queries

Examples