Bạn có biết công ty Just Odd Inventions không? Công việc của công ty này là tạo ra “những phát minh kỳ lạ” (just odd inventions). Sau đây, ta gọi tắt công ty này là JOI.

Để mở rộng hoạt động kinh doanh, công ty JOI quyết định tuyển thêm nhân viên.

Có \(N\) ứng viên, được đánh số từ \(1\) đến \(N\). Mỗi ứng viên có một số nguyên gọi là điểm đánh giá.

Trong đợt tuyển dụng này, công ty sẽ tuyển tất cả các ứng viên có điểm đánh giá không nhỏ hơn một ngưỡng nhất định. Những nhân viên mới được tuyển sẽ được chia thành các nhóm sao cho thỏa mãn điều kiện sau:

• Nếu cả ứng viên \(a\) và ứng viên \(b\), với \(a < b\), đều được tuyển, thì họ thuộc cùng một nhóm khi và chỉ khi mọi ứng viên \(c\) với \(a \le c \le b\) đều được tuyển.

Là người phụ trách nhân sự của công ty JOI, bạn cần ước tính số nhóm được tạo ra trong đợt tuyển dụng này bằng cách xử lý lần lượt \(M\) truy vấn. Truy vấn thứ \(j\) thuộc một trong hai loại sau:

• Tìm số nhóm được tạo ra nếu tuyển tất cả các ứng viên có điểm đánh giá không nhỏ hơn \(B_j\). Loại truy vấn này được gọi là truy vấn hỏi.
• Cập nhật điểm đánh giá của ứng viên \(C_j\) thành \(D_j\). Loại truy vấn này được gọi là truy vấn cập nhật.

Yêu cầu

Cho thông tin về \(M\) truy vấn, hãy viết chương trình tìm số nhóm ứng với mỗi truy vấn hỏi.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N, M\), cách nhau bởi dấu cách: có \(N\) ứng viên và bạn cần xử lý \(M\) truy vấn.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa số nguyên \(A_i\), là điểm đánh giá của ứng viên \(i\) trước khi xử lý các truy vấn.
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le M\)) chứa hai hoặc ba số nguyên, cách nhau bởi dấu cách. Gọi số nguyên đầu tiên là \(T_j\). Nội dung dòng này là một trong hai dạng:
• Nếu \(T_j = 1\), dòng chứa hai số nguyên \(T_j, B_j\). Đây là truy vấn hỏi số nhóm được tạo ra nếu tuyển tất cả các ứng viên có điểm đánh giá không nhỏ hơn \(B_j\).
• Nếu \(T_j = 2\), dòng chứa ba số nguyên \(T_j, C_j, D_j\). Đây là truy vấn cập nhật điểm đánh giá của ứng viên \(C_j\) thành \(D_j\).

Dữ liệu ra

Với mỗi truy vấn hỏi, in ra đầu ra chuẩn số nhóm tương ứng trên một dòng, theo đúng thứ tự các truy vấn.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

• \(1 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le T_j \le 2\) (\(1 \le j \le M\)).
• \(1 \le B_j \le 1\,000\,000\,000\) (\(1 \le j \le M\)).
• \(1 \le C_j \le N\) (\(1 \le j \le M\)).
• \(1 \le D_j \le 1\,000\,000\,000\) (\(1 \le j \le M\)).
• Có ít nhất một chỉ số \(j\) (\(1 \le j \le M\)) sao cho \(T_j = 1\).

Phân nhóm

1. 10 điểm: \(N \le 2\,000\) và \(M \le 2\,000\).
2. 30 điểm: \(T_j = 1\) với mọi \(1 \le j \le M\).
3. 60 điểm: Không có ràng buộc bổ sung.

Ví dụ

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

2
1
2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

0
1
3
3
2

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

2
1
0