Cho tập hợp các đường thẳng có dạng \(y = a \cdot x + b\). Bạn cần hỗ trợ hai loại truy vấn:

• Loại 1: Thêm một đường thẳng \(y = a \cdot x + b\) vào tập hợp.
• Loại 2: Với một giá trị \(x_0\), tìm giá trị \(y = \min(a \cdot x_0 + b)\) trên tất cả các đường thẳng hiện có.

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

• Dòng đầu chứa số lượng truy vấn \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:
  • 1 a b: Thêm đường thẳng \(y = a \cdot x + b\).
  • 2 x: Truy vấn giá trị nhỏ nhất tại điểm \(x\).

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra giá trị nhỏ nhất trên một dòng.

Ví dụ

Input:

4
1 2 3
1 -1 5
2 2
2 0

Output:

3
3

Giải thích: Tại \(x=2\): \(2(2)+3 = 7\), \(-1(2)+5 = 3 \implies \min = 3\). Tại \(x=0\): \(2(0)+3 = 3, -1(0)+5 = 5 \implies \min = 3\).

Ràng buộc & Subtasks