Tý cần giải bài toán sau:

Trong mot he thong dieu khien giao thong thong minh, moi tuyen duong duoc dac trung boi mot ham tuyen tinh \(y = a \cdot x + b\). Tuy nhien, cac tuyen duong co the duoc them moi hoac tam ngung hoat dong.

He thong can tra loi cau hoi: tai mot thoi diem dang xet, tuyen duong nao dang hoat dong cho gia tri nho nhat tai hoanh do \(x\)?

Co \(Q\) thao tac:

• \(1\) \(a\) \(b\): Them duong thang \(y = a \cdot x + b\) vao he thong (duoc gan mot ma so duy nhat).
• \(2\) \(id\): Xoa duong thang co ma so \(id\) (dam bao ton tai).
• \(3\) \(x\): In ra gia tri nho nhat trong cac duong thang dang hoat dong tai \(x\).

Dinh dang dau vao

• Dong dau tien chua so nguyen \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dong tiep theo co dinh dang tren.

Dinh dang dau ra

• Voi moi truy van loai \(3\), in ra mot so nguyen.

Vi du

Input:

9
1 2 1
1 0 5
3 2
3 0
2 1
3 2
3 0
1 -3 10
3 1

Output:

5
5
13
5
8

Giai thich: Them \(y=2x+1\) (id=1), \(y=5\) (id=2). Query \(x=2\): \(\min(5,5)=5\). Query \(x=0\): \(\min(1,5)=1\). Xoa id=1. Query \(x=2\): \(5\). Query \(x=0\): \(5\). Them \(y=-3x+10\) (id=3). Query \(x=1\): \(\min(5,7)=5\).

Rang buoc

• Subtask 1 (20%): \(Q \le 200\).
• Subtask 2 (30%): \(Q \le 5000\).
• Subtask 3 (50%): \(Q \le 10^5\).