Cây Li Chao tìm giá trị lớn nhất \(y = \max(a \cdot x + b)\) thay vì nhỏ nhất.

Định dạng đầu vào

• Dòng 1: Số truy vấn \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo: 1 a b để thêm đường thẳng hoặc 2 x để tìm max tại \(x\).

Định dạng đầu ra

• In ra giá trị cực đại tại các truy vấn loại 2.

Ví dụ

Input:

4
1 2 1
1 -1 10
2 2
2 4

Output:

8
9

Giải thích: Tại \(x=2\): \(\max(2(2)+1, -1(2)+10) = $\max(5, 8) = 8\). Tại \(x=4\): \(\max(2(4)+1, -1(4)+10) = $\max(9, 6) = 9\).

Ràng buộc & Subtasks