Bộ phận nhân sự của tập đoàn nơi Bob làm việc cần quản lý mức lương của \(N\) nhân viên. Mỗi nhân viên i ban đầu có một mức lương là A_i. Để đảm bảo chính sách bảo mật và báo cáo quỹ lương hợp lý, Bob cần thực hiện \(Q\) truy vấn thuộc hai loại:

• 1 pos val: Cập nhật mức lương của nhân viên tại vị trí \(pos\) thành giá trị mới là \(val\).
• 2 min_val max_val: Đếm xem có bao nhiêu nhân viên hiện tại đang có mức lương nằm trong khoảng từ \(min\_val\) đến \(max\_val\).

Hãy giúp Bob viết chương trình xử lý nhanh các truy vấn này.

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

• Dòng đầu chứa hai số nguyên dương \(N\) và Q (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) là mức lương ban đầu của các nhân viên (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong hai loại trên (\(1 \le pos \le N, 1 \le val, min\_val, max\_val \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn loại 2, in ra số lượng nhân viên thỏa mãn trên một dòng.

Ví dụ

Input:

5 4
10 20 30 40 50
2 15 45
1 3 15
2 15 45
2 5 12

Output:

3
3
1

Ràng buộc & Subtasks