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.

Input

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\cdot 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)\bmod 2~.

• 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)\bmod (2\cdot 10^9+1)~

  • ~y:=(y+last)\bmod (2\cdot 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) \bmod size + 1~.

  Dữ liệu đảm bảo ~size > 0~ khi thực hiện thao tác này.

Output

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.

Scoring

Sample Input 1

6
0 1000000000 1000000000
0 1000000 1001000000
0 1000000 999000000
0 1001500 1000001500
1 85072946 2
1 61619603 2

Sample Output 1

0
0
3000000000000
6000000000000
3000000000000
0

Notes

Ta có kết quả sau khi biến đổi và kết quả thực hiện thao tác sau mỗi một trong ~6~ thao tác là:

1. ~t = 0, x = 0, y = 0~. Tập ~P = \{(0,0)\}~ nên hai lần diện tích bao lồi là ~0~.

2. ~t = 0, x = 10^6, y = 10^6~. Tập ~P = \{(0,0), (10^6, 10^6)\}~ nên hai lần diện tích bao lồi là ~0~.

3. ~t = 0, x = 2\cdot 10^6, y = -10^6~. Tập ~P = \{(0,0), (10^6, 10^6), (2\cdot 10^6, -10^6)\}~ nên hai lần diện tích bao lồi là ~3\cdot 10^{12}~.

4. ~t = 0, x = 3000000, y = 0~. Tập ~P = \{(0,0), (10^6, 10^6), (2\cdot 10^6, -10^6), (3\cdot 10^6, 0)\}~ nên hai lần diện tích của bao lồi là ~6\cdot 10^{12}~.

5. ~t = 1, k = 1~. Tập ~P = \{(0,0), (10^6, 10^6), (2\cdot 10^6, -10^6)\}~ nên hai lần diện tích bao lồi là ~3\cdot 10^{12}~.

6. ~t = 1, k = 2~. Tập ~P = \{(0,0)\}~ nên hai lần diện tích bao lồi là ~0~.