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 chỉ đơn thuần là kỳ lạ”. Sau đây, ta gọi tắt công ty là JOI.

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

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

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

• Khi cả ứng viên $a$ và ứng viên $b$ ($a<b$) đều được tuyển, hai nhân viên này thuộc cùng một nhóm khi và chỉ khi tất cả ứng viên $c$ ($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 sẽ ước tính số nhóm được tạo thành trong đợt tuyển dụng này bằng cách xử lý lần lượt tổng cộng $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 thành khi tuyển tất 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 trả lờ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.

Nhiệm vụ

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

Dữ liệu vào

Đọc các dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa các số nguyên $N,M$, cách nhau bởi dấu cách. Điều này cho biết có $N$ ứng viên và bạn sẽ xử lý $M$ truy vấn.
• Dòng thứ $i$ ($1 \le i \le N$) trong $N$ dòng tiếp theo chứa số nguyên $A_i$. Điều này cho biết, trước khi xử lý các truy vấn, điểm đánh giá của ứng viên $i$ là $A_i$.

• Dòng thứ $j$ ($1 \le j \le M$) trong $M$ dòng tiếp theo 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 của dòng thuộc một trong các trường hợp sau.

  1. Khi $T_j=1$, dòng này chứa các số nguyên $T_j,B_j$, cách nhau bởi dấu cách. Điều này cho biết truy vấn thứ $j$ là truy vấn trả lời, yêu cầu tìm số nhóm được tạo thành khi tuyển tất cả ứng viên có điểm đánh giá không nhỏ hơn $B_j$.
  2. Khi $T_j=2$, dòng này chứa các số nguyên $T_j,C_j,D_j$, cách nhau bởi dấu cách. Điều này cho biết truy vấn thứ $j$ là truy vấn cập nhật, đổi điểm đánh giá của ứng viên $C_j$ thành $D_j$.

Dữ liệu ra

In ra đầu ra chuẩn số nhóm tương ứng với từng truy vấn trả lời theo thứ tự, mỗi kết quả trên một dòng.

Giới hạn

Tất cả dữ liệu đầ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 $j$ ($1 \le j \le M$) sao cho $T_j=1$.

Nhiệm vụ con

Nhiệm vụ con 1 [10 điểm]

Thỏa mãn các điều kiện sau.

• $N \le 2\,000$.
• $M \le 2\,000$.

Nhiệm vụ con 2 [30 điểm]

• $T_j=1$ ($1 \le j \le M$).

Nhiệm vụ con 3 [60 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
1
2

Ghi chú

1. Truy vấn thứ nhất là truy vấn trả lời. Khi tuyển ứng viên $1$, $2$, $4$ có điểm đánh giá không nhỏ hơn $5$, ta tạo được hai nhóm: một nhóm gồm ứng viên $1$ và $2$, và một nhóm gồm ứng viên $4$. Vì vậy, in ra $2$.
2. Truy vấn thứ hai là truy vấn cập nhật. Điểm đánh giá của ứng viên $4$ được cập nhật thành $1$.
3. Truy vấn thứ ba là truy vấn trả lời. Khi tuyển ứng viên $1$ và $2$ có điểm đánh giá không nhỏ hơn $5$, ta tạo được một nhóm gồm ứng viên $1$ và $2$. Vì vậy, in ra $1$.
4. Truy vấn thứ tư là truy vấn trả lời. Khi tuyển ứng viên $1$, $2$, $3$, $5$ có điểm đánh giá không nhỏ hơn $3$, ta tạo được hai nhóm: một nhóm gồm ứng viên $1$, $2$, $3$, và một nhóm gồm ứng viên $5$. Vì vậy, in ra $2$.

Dữ liệu vào 2

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

Dữ liệu ra 2

0
1
3
3
2

Ghi chú

Ví dụ đầu vào 2 thỏa mãn các giới hạn của nhiệm vụ con 2.

Dữ liệu vào 3

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

Dữ liệu ra 3

2
1
0