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

Nam dang xay dung mot he thong dinh vi cho robot tu hanh. Moi duong di cua robot duoc mo ta boi mot duong thang \(y = a \cdot x + b\). He thong can xac dinh vi tri xa nhat ma robot co the di chuyen tu mot moc dinh vi cho truoc.

Cu the, co \(Q\) thao tac, moi thao tac thuoc mot trong hai loai:

• Them mot duong di moi \(y = a \cdot x + b\).
• Voi mot vi tri \(x\) cho truoc, hay tinh gia tri nho nhat trong tat ca cac duong di hien co tai diem do.

Dinh dang dau vao

• Dong dau tien chua so nguyen \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dong tiep theo, moi dong co dinh dang:
  • \(1\) \(a\) \(b\): Them duong thang \(y = a \cdot x + b\) (\(|a|, |b| \le 10^9\)).
  • \(2\) \(x\): Truy van gia tri nho nhat tai \(x\) (\(|x| \le 10^9\)).

Dinh dang dau ra

• Voi moi truy van loai \(2\), in ra mot so nguyen la gia tri nho nhat.

Vi du

Input:

8
1 2 1
1 0 5
2 2
2 0
1 -3 10
2 3
2 -1
2 2

Output:

5
1
1
-1
4

Giai thich: Sau khi them \(y = 2x + 1\) va \(y = 5\), query \(x = 2\): \(\min(5, 5) = 5\). Query \(x = 0\): \(\min(1, 5) = 1\). Sau khi them \(y = -3x + 10\), query \(x = 3\): \(\min(7, 5, 1) = 1\). Query \(x = -1\): \(\min(-1, 5, 13) = -1\). Query \(x = 2\): \(\min(5, 5, 4) = 4\).

Rang buoc

• Subtask 1 (20%): \(Q \le 200\).
• Subtask 2 (30%): \(Q \le 5000\).
• Subtask 3 (50%): \(Q \le 10^5\). Cac gia tri \(x\) trong truy van nam trong doan \([-10^9, 10^9]\).