Опукла оболонка (запити)

Задано множину точок на площині, а також $N$ операцій, що модифікують цю множину. Кожна операція може бути одного з двох наступних типів:

1. Додати до множини точку з цілими координатами. При цьому абсциса (тобто $X$ координата) нової точки є строго більшою за абсциси всіх інших точок, які вже знаходяться у множині.

2. Видалити з множини точку з найбільшою абсцисою.

Напишіть програму, яка за заданою послідовністю з N операцій промоделює їх виконання та після кожної з них виведе подвоєну площу опуклої оболонки точок множини. Перед виконанням першої операції множина точок є порожньою. Вважатимемо, що площа опуклої оболонки порожньої множини точок рівна нулю.

Опуклою оболонкою множини точок на площині називається опуклий багатокутник найменшої площі, який містить всі точки з множини. Багатокутник називається опуклим, якщо відрізок, що сполучає будь-які дві його точки цілком належить цьому багатокутнику. Тут під багатокутником розуміється границя фігури разом з її внутрішністю.

Вхідні дані

Перший рядок містить одне ціле число: $N(1\le N\le 100^{\prime }000)$ – кількість операцій, які потрібно виконати. Наступні $N$ рядків містять по три цілих числа – інформацію про операції у зашифрованому форматі. Для того, щоб отримати параметри операції з номером i, потрібно зчитати три цілих числа $T\ast$, $X\ast$ та $Y\ast$ $(0\le T\ast \le 1,0\le X\ast ,Y\ast \le 2^{\prime }000^{\prime }000^{\prime }000)$ з $(i+1)$-го рядку, після чого отримати число $T$ за наступною формулою: $T=(T\ast +S)\mathrm{mod}2$, де $S$ - це подвоєна площа опуклої оболонки точок множини до виконання операції з номером $i$. Можна переконатись, що $S$ завжди є цілим числом.

1. Якщо $T=0$, то чергова операція першого типу і координати $(X,Y)$ нової точки отримуються за наступними формулами:

   • $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$.

   Тут $L$ – це максимальна з абсцис усіх точок з множини. Якщо множина порожня, то $L=-1^{\prime }000^{\prime }000^{\prime }000$.

2. Якщо $T=1$, то потрібно $K$ разів виконати операцію другого типу. Число $K$ знаходиться за формулою: $K=((X\ast +Y\ast +S)\mathrm{mod}Q)+1$. Тут $Q$ – це кількість точок у множині.

Гарантується, що при правильній розшифровці всіх операцій виконуються наступні обмеження:

1. Координати усіх точок, які додаються до множині, не перевищують $1^{\prime }000^{\prime }000^{\prime }000$ за модулем.

2. При додаванні нової точки її абсциса є строго більшою за абсциси усіх точок, які вже лежать в множині.

3. Операція видалення застосовується лише до непорожньої множини точок.

Вихідні дані

Потрібно вивести рівно $N$ рядків. В рядок з номером i потрібно вивести подвоєну площу опуклої оболонки множини точок, яка утворилася після виконання перших $i$ операцій. Якщо множина точок виявилася порожньою, то площу її опуклої оболонки вважати рівною 0.

Приклади

Примітка

Після розшифрування тест виглядає таким чином:

• $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$

Оцінювання

Набір тестів складається з 4 окремих блоків, з такими додатковими обмеженнями:

• 15% тестів: $N\le 300$

• 15% тестів: $N\le 3000$

• 20% тестів $N\le 100000$, кількість рядків, у яких $T=1$ (після розшифрування) не перевищує 100

• 50% тестів: $N\le 100000$