Opuk qabıq (sorğular)

Giriş

Birinci sətirdə bir tam ədəd var: $N$ $(1 \leq N \leq 100000)$ (1 \leq N \leq 100\,000) — yerinə yetiriləcək əməliyyatların sayı. Sonrakı $N$ sətirin hər birində üç tam ədəd verilib, əməliyyatlar kodlaşdırılmış formadadır. $i$ -ci əməliyyatın parametrlərini tapmaq üçün $(i + 1)$ (i + 1)-ci sətirdən üç tam ədəd $T^{*}$ T^*, $X^{*}$ X^* və $Y^{*}$ Y^* $(0 \leq T^{*} \leq 1, 0 \leq X^{*}, Y^{*} \leq 2000000000)$ (0 \leq T^* \leq 1,\ 0 \leq X^*, Y^* \leq 2\,000\,000\,000) oxuyun, sonra $T$ qiymətini aşağıdakı düsturla hesablayın:

T = (T^{*} + S) mod 2

T = (T^* + S) \bmod 2

burada $S$ — əməliyyat $i$ yerinə yetirilməzdən əvvəl nöqtələrin konveks örtüyünün ikiqat sahəsidir. Zəmanət verilir ki, $S$ həmişə tam ədəddir.

Əgər $T = 0$ T = 0-dırsa, cari əməliyyat birinci tipdədir və yeni nöqtənin $(X, Y)$ (X, Y) koordinatları aşağıdakı kimi hesablanır:
- $X = L + ((S + X^{*}) mod 2000000001)$ X = L + ((S + X^*) \bmod 2\,000\,000\,001),
- $Y = ((Y^{*} + S) mod 2000000001) - 1000000000$ Y = ((Y^* + S) \bmod 2\,000\,000\,001) - 1\,000\,000\,000.
Burada $L$ çoxluqdakı bütün nöqtələrin maksimum $X$ koordinatıdır. Əgər çoxluq boşdursa, onda $L = - 1000000000$ L = -1\,000\,000\,000.
Əgər $T = 1$ T = 1-dirsə, ikinci tip əməliyyatı $K$ dəfə yerinə yetirin. $K$ aşağıdakı düsturla müəyyən olunur:
$K = ((X^{*} + Y^{*} + S) mod Q) + 1$
K = ((X^* + Y^* + S) \bmod Q) + 1
Burada $Q$ - çoxluqdakı nöqtələrin sayıdır.

Zəmanət verilir ki, bütün əməliyyatlar düzgün deşifrovka olunduqda aşağıdakı şərtlər təmin olunur:

Çoxluğa əlavə olunan bütün nöqtələrin koordinatlarının modulu $1000000000$ 1\,000\,000\,000-dan böyük deyil.
Yeni nöqtə əlavə olunduqda onun $X$ koordinatı artıq çoxluqda olan bütün nöqtələrin $X$ koordinatlarından mütləq böyükdür.
Silmə əməliyyatı yalnız qeyri-boş çoxluğa tətbiq edilir.

Çıxış

Dəqiq $N$ sətir çap edin. $i$ -ci sətirə, ilk $i$ əməliyyatdan sonra alınan nöqtələr çoxluğunun konveks örtüyünün ikiqat sahəsini çıxışa verin. Əgər nöqtələr çoxluğu boşdursa, qəbul edin ki, onun konveks örtüyünün sahəsi $0$ -dır.

Nümunələr

Nümunə 1

Loading

Qeyd

Deşifrovkadan sonra test belə olacaq:

$T = 0, X = 0, Y = 0$ T = 0,\ X = 0,\ Y = 0
$T = 0, X = 1000000, Y = 1000000$ T = 0,\ X = 1\,000\,000,\ Y = 1\,000\,000
$T = 0, X = 2000000, Y = - 1000000$ T = 0,\ X = 2\,000\,000,\ Y = -1\,000\,000
$T = 0, X = 3000000, Y = 0$ T = 0,\ X = 3\,000\,000,\ Y = 0
$T = 1, K = 1$ T = 1,\ K = 1
$T = 1, K = 2$ T = 1,\ K = 2

Bal hesablama

Testlər $4$ ayrıca blokdan ibarətdir və bunlara əlavə məhdudiyyətlər qoyulub:

$15%$ testlər: $N \leq 300$ N \leq 300
$15%$ testlər: $N \leq 3000$ N \leq 3\,000
$20%$ testlər: $N \leq 100000$ N \leq 100\,000, burada deşifrovkadan sonra $T = 1$ T = 1 olan sətirlərin sayı $100$ -dən çox deyil
$50%$ testlər: $N \leq 100000$ N \leq 100\,000