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

Trong mot he thong quan ly phien ban du lieu, moi thay doi ve tuyen duong duoc ghi lai nhu mot phien ban moi. Nguoi dung co the them mot duong thang vao phien ban hien tai de tao phien ban moi, hoac truy van gia tri tren mot phien bat ky.

Co \(Q\) thao tac:

• \(1\) \(a\) \(b\): Them duong thang \(y = a \cdot x + b\) vao phien ban hien tai de tao phien ban moi. Phien ban moi tro thanh phien ban hien tai.
• \(2\) \(k\) \(x\): Truy van gia tri nho nhat tai \(x\) tren phien ban thu \(k\).

Ban dau, phien ban \(0\) la phien ban rong (khong co duong thang nao).

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 \(2\), in ra mot so nguyen.

Vi du

Input:

7
1 2 1
1 0 5
2 1 2
2 2 0
1 -3 10
2 3 3
2 5 0

Output:

5
1
1
4000000000000000000

Giai thich: Phien ban 1: \(y=2x+1\). Phien ban 2: \(y=2x+1\), \(y=5\). Truy van phien ban 1 tai \(x=2\): \(2\times 2 + 1 = 5\). Truy van phien ban 2 tai \(x=0\): \(\min(1, 5) = 1\). Them \(y=-3x+10\) duoc phien ban 3. Truy van tai \(x=3\): \(\min(7,5,1) = 1\). Truy van phien ban 5 (khong ton tai) tai \(x=0\): khong co duong thang nao, tra ve gia tri vo cung lon.

Rang buoc

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