Diện tích bao lồi

Cho $P$ là một tập các điểm trên mặt phẳng. Ban đầu tập $P$ rỗng. Có một dãy gồm $n$ thao tác trên tập điểm này. Mỗi thao tác thuộc một trong hai dạng sau:

1. Thêm một điểm có toạ độ nguyên vào tập $P$. Trong thao tác này điểm được thêm vào có hoành độ lớn hơn hẳn hoành độ các điểm hiện đang nằm trong $P$.
2. Xoá khỏi $P$ một số điểm có hoành độ lớn nhất.

Ta gọi bao lồi của tập $P$ là đa giác lồi nhỏ nhất chứa tập $P$. Nhiệm vụ của bạn là tính diện tích của bao lồi sau mỗi thao tác.

Dữ liệu vào

Dòng đầu tiên gồm một số nguyên $n$ ($n\le {10}^5$): số lượng thao tác.

Mỗi dòng trong $n$ dòng tiếp theo gồm ba số nguyên $t,x,y$ ($0\le t\le 1$, $0\le x,y\le 2·{10}^9$). Gọi $last$, $maxx$, $size$ lần lượt là hai lần diện tích bao lồi, hoành độ lớn nhất, kích thước của tập $P$ trước khi thực hiện thao tác hiện tại. Ban đầu $last=0$ và nếu $size=0$, ta coi $maxx=-{10}^9$. Ta biến đổi $t:=(t+last)mod2$.

Nếu $t=0$, khi đó ta thực hiện thao tác $1$, thêm điểm $(x,y)$ vào tập sau khi biến đổi như sau:

• $x:=maxx+(last+x)mod(2·{10}^9+1)$;
• $y:=(y+last)mod(2·{10}^9+1)-{10}^9$.

Dữ liệu đảm bảo $|x|,|y|\le {10}^9$ sau khi biến đổi.

Nếu $t=1$, ta thực hiện thao tác loại $2$, xoá $k$ điểm có hoành độ lớn nhất với $k=(x+y+last)modsize+1$. Dữ liệu đảm bảo $size>0$ khi thực hiện thao tác này.

Dữ liệu ra

Sau mỗi thao tác, in ra hai lần diện tích bao lồi của tập $P$ trên một dòng.

Ràng buộc

• $n\le {10}^5$;
• $0\le t\le 1$, $0\le x,y\le 2·{10}^9$;
• sau khi biến đổi: $|x|,|y|\le {10}^9$; khi xoá thì $size>0$.

Subtasks

• Subtask 1 ($15\%$ số điểm): $n\le 300$.
• Subtask 2 ($15\%$ số điểm): $n\le 3000$.
• Subtask 3 ($20\%$ số điểm): số lượng thao tác loại $2$ không quá $100$.
• Subtask 4 ($50\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ