Şər'in Kökü

Sizə $n$ rəqəmindən ibarət $a_1,a_2,\dots ,a_n$ çoxluq verilir.

Növbəti $3$ növ sorğu verilir:

• 1 x — müsbət tam rəqəmi $x$-i çoxluğa əlavə edin

• 2 x — çoxluqdan $x$ rəqəminin bir nüsxəsini silin. Bu əməliyyatı yerinə yetirərkən, çoxluqda ən azı bir $x$ olduğu təmin edilir.

• 3 x — çoxluqda $p$ və $q$ elementlərinin cütlüyünün sayını tapın ki, $\lfloor \frac{p}{q}\rfloor =x$ olsun, burada $\lfloor k\rfloor$ $k\ge \lfloor k\rfloor$ olan ən böyük tam rəqəmdir. Bu sorğu alınarkən, hazırda ən azı bir elementin çoxluqda olduğu təmin edilir. Qeyd edək ki, $x$ $1$-dən böyükdür.

Siz $q$ növü sorğunu yerinə yetirməlisiniz. Hər $3$-cü növ sorğusu üçün, tələb olunan cütlük sayını çıxarmanız lazımdır.

Giriş verilənləri

İlk sətirdə $n$ ($1\le n\le 10^5$) tam rəqəmi verilir — əvvəlki arraydəki elementlərin sayı.

İkinci sətirdə $n$ tam rəqəmi $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^5$) verilir — çoxluğun elementləri.

Üçüncü sətirdə $q$ ($1\le q\le 10^5$) tam rəqəmi verilir — sorğuların sayı.

Son $q$ sətirdə, hər bir sorğu ayrı sətirə verilir. Hər bir sorğuda iki rəqəm $type$ ($1\le type\le 3$) və $x$ olur $(\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}$ burada $type$ sorğunun növü, $x$ isə sorğuda verilən rəqəmdir. Əmin edilir ki, ən azı bir $3$-cü növ sorğu var.

Çıxış verilənləri

Hər bir $3$-cü növ sorğusu üçün, tələb olunan cütlük sayını çıxarmanız lazımdır.

Nümunələr

Qiymətləndirmə

1. ($32$ xal): $n\le 500$, $q\le 500$, $a_i\le 500$, hər bir sorğuda $x\le 500$;

2. ($71$ xal): $a_i\le 1000$, hər bir sorğuda $x\le 1000$;

3. ($99$ xal): $1$ və $2$ növ sorğular yoxdur;

4. ($99$ xal): $2$ növ sorğular yoxdur;

5. ($99$ xal): əlavə məhdudiyyətlər yoxdur.