Tý có lưới tọa độ nguyên. Có \(Q\) truy vấn thuộc hai loại:

• add x1 y1 x2 y2 val: thêm một hình chữ nhật có góc trái dưới \((x1, y1)\), góc phải trên \((x2, y2)\) với giá trị \(val\).
• query x y: tìm giá trị lớn nhất trong tất cả hình chữ nhật chứa điểm \((x, y)\).

Nếu không có hình chữ nhật nào chứa điểm, in ra \(0\).

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

• Dòng 1: số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp: mỗi dòng là một truy vấn như mô tả.
• Các tọa độ: \(1 \le x1 \le x2 \le 10^9\), \(1 \le y1 \le y2 \le 10^9\), \(1 \le val \le 10^9\).

Định dạng đầu ra

• Với mỗi truy vấn query, in ra một số nguyên là giá trị lớn nhất.

Ví dụ

Input:

7
add 1 1 5 5 10
add 2 2 4 4 20
query 3 3
query 1 1
query 6 6
add 1 1 10 10 5
query 3 3

Output:

20
10
0
20

Ràng buộc