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