Cho một tập hợp các đoạn thẳng trên mặt phẳng tọa độ \(Oxy\). Ban đầu tập hợp này rỗng. Bạn cần xử lý \(Q\) truy vấn thuộc một trong hai loại sau:

• 1 l r a b: Thêm một đoạn thẳng \(y = a \cdot x + b\) có hiệu lực đối với các số nguyên \(x \in [l, r]\).
• 2 x: Tìm giá trị lớn nhất của \(y = a \cdot x + b\) tại tọa độ \(x\) trong tất cả các đoạn thẳng đang có trong tập hợp mà phủ điểm \(x\).

Input

• Dòng đầu tiên chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)) — số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng nêu trên.
• Ràng buộc đoạn thẳng: \(1 \le l \le r \le 10^9\), \(-10^9 \le a, b \le 10^9\).
• Ràng buộc tọa độ truy vấn: \(1 \le x \le 10^9\).

Output

• Với mỗi truy vấn loại \(2\), in ra giá trị lớn nhất tìm được trên một dòng. Nếu không có đoạn thẳng nào phủ điểm \(x\), in ra NO.

Example

7
2 10
1 1 5 2 3
1 3 8 -1 10
2 2
2 4
1 2 4 5 -1
2 3

NO
7
11
14

Scoring

• Subtask 1 (30% số điểm): \(1 \le Q \le 1000\).
• Subtask 2 (70% số điểm): \(1 \le Q \le 10^5\).