Опук qabıq (sorğular)

Verilmiş müstəvi üzərində bir nöqtələr çoxluğu və bu çoxluğu dəyişdirən $N$ əməliyyat verilir. Hər bir əməliyyat aşağıdakı iki növdən biri ola bilər:

1. Çoxluğa tam koordinatlı bir nöqtə əlavə edin. Bu zaman yeni nöqtənin absissası (yəni $X$ koordinatı) artıq çoxluqda olan bütün digər nöqtələrin absissalarından mütləq böyük olmalıdır.

2. Çoxluqdan ən böyük absissalı nöqtəni silin.

Verilmiş $N$ əməliyyat ardıcıllığına əsasən, onların icrasını modelləşdirən və hər bir əməliyyatdan sonra çoxluqdakı nöqtələrin konveks qabığının ikiqat sahəsini çıxaran bir proqram yazın. İlk əməliyyatın icrasından əvvəl nöqtələr çoxluğu boşdur. Boş nöqtələr çoxluğunun konveks qabığının sahəsinin sıfır olduğunu qəbul edək.

Müstəvi üzərində nöqtələr çoxluğunun konveks qabığı, çoxluqdakı bütün nöqtələri əhatə edən ən kiçik sahəli konveks çoxbucaqlıdır. Çoxbucaq konveks adlanır, əgər onun istənilən iki nöqtəsini birləşdirən seqment tamamilə həmin çoxbucağa aid olarsa. Burada çoxbucaq dedikdə, fiqurun sərhədi və onun daxili nəzərdə tutulur.

Giriş verilənləri

Birinci sətir bir tam ədəd ehtiva edir: $N(1\le N\le 100^{\prime }000)$ – icra olunmalı əməliyyatların sayı. Növbəti $N$ sətir hər biri üç tam ədəd ehtiva edir – şifrlənmiş formatda əməliyyatlar haqqında məlumat. $i$ nömrəli əməliyyatın parametrlərini əldə etmək üçün $(i+1)$-ci sətirdən üç tam ədəd $T\ast$, $X\ast$ və $Y\ast$ $(0\le T\ast \le 1,0\le X\ast ,Y\ast \le 2^{\prime }000^{\prime }000^{\prime }000)$ oxumaq lazımdır, sonra isə $T$ ədədini aşağıdakı düsturla əldə etmək lazımdır: $T=(T\ast +S)\mathrm{mod}2$, burada $S$ – $i$ nömrəli əməliyyatın icrasından əvvəl çoxluqdakı nöqtələrin konveks qabığının ikiqat sahəsidir. $S$-in həmişə tam ədəd olduğuna əmin ola bilərsiniz.

1. Əgər $T=0$ olarsa, növbəti əməliyyat birinci tipdədir və yeni nöqtənin $(X,Y)$ koordinatları aşağıdakı düsturlarla əldə edilir:

   • $X=L+((S+X\ast )\mathrm{mod}{2}^{\prime }000^{\prime }000^{\prime }001)$,

   • $Y=((Y\ast +S)\mathrm{mod}{2}^{\prime }000^{\prime }000^{\prime }001)–1^{\prime }000^{\prime }000^{\prime }000$.

   Burada $L$ – çoxluqdakı bütün nöqtələrin absissalarının maksimumudur. Əgər çoxluq boşdursa, onda $L=-1^{\prime }000^{\prime }000^{\prime }000$.

2. Əgər $T=1$ olarsa, ikinci tip əməliyyatı $K$ dəfə icra etmək lazımdır. $K$ ədədi aşağıdakı düsturla tapılır: $K=((X\ast +Y\ast +S)\mathrm{mod}Q)+1$. Burada $Q$ – çoxluqdakı nöqtələrin sayıdır.

Doğru şifrələmə ilə bütün əməliyyatların icrası zamanı aşağıdakı məhdudiyyətlər təmin edilir:

1. Çoxluğa əlavə edilən bütün nöqtələrin koordinatları modul üzrə $1^{\prime }000^{\prime }000^{\prime }000$-dan çox deyil.

2. Yeni nöqtə əlavə edilərkən onun absissası artıq çoxluqda olan bütün nöqtələrin absissalarından mütləq böyükdür.

3. Silmə əməliyyatı yalnız boş olmayan nöqtələr çoxluğuna tətbiq edilir.

Çıxış verilənləri

Dəqiq $N$ sətir çıxarılmalıdır. $i$ nömrəli sətirdə, ilk $i$ əməliyyatın icrasından sonra yaranan nöqtələr çoxluğunun konveks qabığının ikiqat sahəsi çıxarılmalıdır. Əgər nöqtələr çoxluğu boşdursa, onun konveks qabığının sahəsini sıfır hesab edin.

Nümunələr

Qeyd

Şifrələmədən sonra test belə görünür:

• $T=0,X=0,Y=0$

• $T=0,X=1000000,Y=1000000$

• $T=0,X=2000000,Y=-1000000$

• $T=0,X=3000000,Y=0$

• $T=1,K=1$

• $T=1,K=2$

Qiymətləndirmə

Test dəsti 4 ayrı blokdan ibarətdir, əlavə məhdudiyyətlərlə:

• 15% testlər: $N\le 300$

• 15% testlər: $N\le 3000$

• 20% testlər $N\le 100000$, $T=1$ olan sətirlərin sayı (şifrələmədən sonra) 100-dən çox deyil

• 50% testlər: $N\le 100000$