Nhiệm vụ của bạn là xử lý hiệu quả các loại truy vấn sau:

• Thêm một đường thẳng \(ax+b\)

• Tìm giá trị lớn nhất tại vị trí \(x\) trong số các đường thẳng

Input

Dòng đầu tiên chứa một số nguyên \(n\): số lượng truy vấn.

\(n\) dòng tiếp theo mô tả các truy vấn. Định dạng của mỗi dòng là "1 \(a\) \(b\)" hoặc "2 \(x\)".

Bạn có thể giả sử rằng truy vấn đầu tiên có loại 1.

Output

In ra đáp án cho mỗi truy vấn loại 2.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(-10^9 \le a,b \le 10^9\)

• \(0 \le x \le 10^5\)

Example

6
1 1 2
2 1
2 3
1 0 4
2 1
2 3

3
5
4
5