Задано множину точок на площині, а також $N$ операцій, що модифікують цю множину. Кожна операція може бути одного з двох наступних типів: \begin{enumerate} \item Додати до множини точку з цілими координатами. При цьому абсциса (тобто $X$ координата) нової точки є строго більшою за абсциси всіх інших точок, які вже знаходяться у множині. \item Видалити з множини точку з найбільшою абсцисою. \end{enumerate} Напишіть програму, яка за заданою послідовністю з N операцій промоделює їх виконання та після кожної з них виведе подвоєну площу опуклої оболонки точок множини. Перед виконанням першої операції множина точок є порожньою. Вважатимемо, що площа опуклої оболонки порожньої множини точок рівна нулю. Опуклою оболонкою множини точок на площині називається опуклий багатокутник найменшої площі, який містить всі точки з множини. Багатокутник називається опуклим, якщо відрізок, що сполучає будь-які дві його точки цілком належить цьому багатокутнику. Тут під багатокутником розуміється границя фігури разом з її внутрішністю. \InputFile Перший рядок містить одне ціле число: $N (1 \le N \le 100'000)$ – кількість операцій, які потрібно виконати. Наступні $N$ рядків містять по три цілих числа – інформацію про операції у зашифрованому форматі. Для того, щоб отримати параметри операції з номером i, потрібно зчитати три цілих числа $T*$, $X*$ та $Y*$ $(0 \le T* \le 1, 0 \le X*, Y* \le 2'000'000'000)$ з $(i+1)$-го рядку, після чого отримати число $T$ за наступною формулою: $T = (T* + S) \mod 2$, де $S$ - це подвоєна площа опуклої оболонки точок множини до виконання операції з номером $i$. Можна переконатись, що $S$ завжди є цілим числом. \begin{enumerate} \item Якщо $T=0$, то чергова операція першого типу і координати $(X,Y)$ нової точки отримуються за наступними формулами: \begin{itemize} \item $X=L+((S+X*) \mod 2'000'000'001)$, \item $Y = ((Y*+S) \mod 2'000'000'001) \ – \ 1'000'000'000$. \end{itemize} Тут $L$ – це максимальна з абсцис усіх точок з множини. Якщо множина порожня, то $L=-1'000'000'000$. \item Якщо $T=1$, то потрібно $K$ разів виконати операцію другого типу. Число $K$ знаходиться за формулою: $K= ((X*+Y*+S) \mod Q)+1$. Тут $Q$ – це кількість точок у множині. \end{enumerate} Гарантується, що при правильній розшифровці всіх операцій виконуються наступні обмеження: \begin{enumerate} \item Координати усіх точок, які додаються до множині, не перевищують $1'000'000'000$ за модулем. \item При додаванні нової точки її абсциса є строго більшою за абсциси усіх точок, які вже лежать в множині. \item Операція видалення застосовується лише до непорожньої множини точок. \end{enumerate} \OutputFile Потрібно вивести рівно $N$ рядків. В рядок з номером i потрібно вивести подвоєну площу опуклої оболонки множини точок, яка утворилася після виконання перших $i$ операцій. Якщо множина точок виявилася порожньою, то площу її опуклої оболонки вважати рівною 0. \Scoring Набір тестів складається з 4 окремих блоків, з такими додатковими обмеженнями: \begin{itemize} \item 15\% тестів: $N \le 300$ \item 15\% тестів: $N \le 3000$ \item 20\% тестів $N \le 100 000$, кількість рядків, у яких $T = 1$ (після розшифрування) не перевищує 100 \item 50\% тестів: $N \le 100 000$ \end{itemize} \Note Після розшифрування тест виглядає таким чином: \begin{itemize} \item $T = 0, X = 0, Y = 0$ \item $T = 0, X = 1000000, Y = 1000000$ \item $T = 0, X = 2000000, Y = -1000000$ \item $T = 0, X = 3000000, Y = 0$ \item $T = 1, K = 1$ \item $T = 1, K = 2$ \end{itemize}