The Root of Evil

You are given a multiset $a_1,a_2,\dots ,a_n$ consisting of $n$ numbers.

There are $3$ types of queries you are given next:

• 1 x — add the positive integer number $x$ to the multiset

• 2 x — delete one occurrence of $x$ from the multiset. When performing this operation, it is guaranteed that there is at least one $x$ in the multiset.

• 3 x — find the number of such pairs of elements $p$ and $q$ in the multiset that $\lfloor \frac{p}{q}\rfloor =x$, where $\lfloor k\rfloor$ is the largest such integer number that $k\ge \lfloor k\rfloor$. It is guaranteed that currently there is at least one element in the multiset when getting this query. Note that $x$ is bigger than $1$.

You need to perform $q$ such queries. For every query of the $3$-rd type, you need to output the required number of pairs of numbers.

Input

The first line has an integer $n$ ($1\le n\le 10^5$) — the number of elements in the initial array.

In the second line there are $n$ integer numbers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^5$) — the elements of the multiset.

In the third line you are given a number $q$ ($1\le q\le 10^5$) — the number of queries.

In the last $q$ lines, there are queries on a separate line. Every query contains two numbers $type$ ($1\le type\le 3$) and $x$ $(\begin{array}{c}\left[\begin{array}{c}1\le x\le 10^5,type\le 2\\ 2\le x\le 10^5,type=3\end{array}\right)\end{array}$ where $type$ is a type of query and $x$ is a number given in a query. It is guaranteed that there is at least $1$ query of type $3$.

Output

For every query of $3$-rd type, you need to output the needed amount of pairs for the given $x$.

Examples

Scoring

1. ($32$ points): $n\le 500$, $q\le 500$, $a_i\le 500$, in each query $x\le 500$;

2. ($71$ points): $a_i\le 1000$, in each query $x\le 1000$;

3. ($99$ points): there are no queries of $1$ and $2$ type;

4. ($99$ points): there are no queries of $2$ type;

5. ($99$ points): no additional constraints.