An đang lập trình một hệ thống mô phỏng thiên văn học quan sát bầu trời dưới dạng mặt phẳng tọa độ hai chiều cực kỳ rộng lớn. Thiên hà này có tọa độ giới hạn cực rộng từ \(1\) đến \(10^9\) ở cả hai chiều trục \(x\) và \(y\). Ban đầu, không có ngôi sao nào trên bầu trời. An thực hiện ghi nhận và quan sát qua \(Q\) sự kiện xảy ra tuần tự:

• 1 x y: Một ngôi sao mới xuất hiện (hoặc được ghi nhận thêm một lượng độ sáng là 1) tại tọa độ nguyên \((x, y)\).
• 2 x1 y1 x2 y2: An muốn đếm tổng số lượng ngôi sao (tính cả độ sáng trùng) hiện đang nằm trong vùng hình chữ nhật giới hạn từ tọa độ \(x_1\) đến \(x_2\) và từ \(y_1\) đến \(y_2\).

Vì kích thước bầu trời quá lớn nhưng số lượng sự kiện \(Q\) lại nhỏ, hãy thiết kế giải pháp lập trình tối ưu giúp An.

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

• Dòng đầu chứa số nguyên dương \(Q\) (\(1 \le Q \le 1000\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một sự kiện thuộc một trong hai định dạng trên (\(1 \le x, x_1, x_2 \le 10^9, 1 \le y, y_1, y_2 \le 10^9, x_1 \le x_2, y_1 \le y_2\)).

Định dạng đầu ra

• Với mỗi sự kiện loại 2, in ra tổng số lượng ngôi sao đếm được.

Ví dụ

Input:

4
1 5 10
1 15 20
2 1 1 100 100
2 1 1 10 15

Output:

2
1