Задано множину точок на площині, а також N операцій, що модифікують цю множину. Кожна операція може бути одного з двох наступних типів:
Додати до множини точку з цілими координатами. При цьому абсциса (тобто X координата) нової точки є строго більшою за абсциси всіх інших точок, які вже знаходяться у множині.
Видалити з множини точку з найбільшою абсцисою.
Напишіть програму, яка за заданою послідовністю з N операцій промоделює їх виконання та після кожної з них виведе подвоєну площу опуклої оболонки точок множини. Перед виконанням першої операції множина точок є порожньою. Вважатимемо, що площа опуклої оболонки порожньої множини точок рівна нулю.
Опуклою оболонкою множини точок на площині називається опуклий багатокутник найменшої площі, який містить всі точки з множини. Багатокутник називається опуклим, якщо відрізок, що сполучає будь-які дві його точки цілком належить цьому багатокутнику. Тут під багатокутником розуміється границя фігури разом з її внутрішністю.
Перший рядок містить одне ціле число: N(1≤N≤100′000) – кількість операцій, які потрібно виконати. Наступні N рядків містять по три цілих числа – інформацію про операції у зашифрованому форматі. Для того, щоб отримати параметри операції з номером i, потрібно зчитати три цілих числа T∗, X∗ та Y∗ (0≤T∗≤1,0≤X∗,Y∗≤2′000′000′000) з (i+1)-го рядку, після чого отримати число T за наступною формулою: T=(T∗+S)mod2, де S - це подвоєна площа опуклої оболонки точок множини до виконання операції з номером i. Можна переконатись, що S завжди є цілим числом.
Якщо T=0, то чергова операція першого типу і координати (X,Y) нової точки отримуються за наступними формулами:
X=L+((S+X∗)mod2′000′000′001),
Y=((Y∗+S)mod2′000′000′001) – 1′000′000′000.
Тут L – це максимальна з абсцис усіх точок з множини. Якщо множина порожня, то L=−1′000′000′000.
Якщо T=1, то потрібно K разів виконати операцію другого типу. Число K знаходиться за формулою: K=((X∗+Y∗+S)modQ)+1. Тут Q – це кількість точок у множині.
Гарантується, що при правильній розшифровці всіх операцій виконуються наступні обмеження:
Координати усіх точок, які додаються до множині, не перевищують 1′000′000′000 за модулем.
При додаванні нової точки її абсциса є строго більшою за абсциси усіх точок, які вже лежать в множині.
Операція видалення застосовується лише до непорожньої множини точок.
Потрібно вивести рівно 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≤300
15% тестів: N≤3000
20% тестів N≤100000, кількість рядків, у яких T=1 (після розшифрування) не перевищує 100
50% тестів: N≤100000