Tý có một thư viện số hóa lưu trữ \(N\) tài liệu theo thứ tự đánh số. Mỗi tài liệu có một mã chủ đề (số nguyên dương). Thủ thư cần thực hiện \(Q\) thao tác gồm hai loại:

• 1 pos val: Cập nhật mã chủ đề của tài liệu tại vị trí \(pos\) thành giá trị \(val\).
• 2 L R: Truy vấn xem trong đoạn tài liệu từ \(L\) đến \(R\) có bao nhiêu mã chủ đề khác nhau (tính tại thời điểm hiện tại).

Hãy giúp thủ thư xử lý các thao tác.

Đị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 thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác theo định dạng trên.

Định dạng đầu ra

• Với mỗi thao tác loại \(2\), in ra số mã chủ đề khác nhau trong đoạn tương ứng.

Ví dụ

Input:

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

Output:

3
2
4
2

Giải thích:

• Ban đầu \([1,2,3,2,1]\).
• \([1,3]\): \(\{1,2,3\}\) → 3 khác nhau.
• Cập nhật \(pos=3\) thành \(2\): \([1,2,2,2,1]\).
• \([1,5]\): \(\{1,2\}\) → 2 khác nhau.
• Cập nhật \(pos=2\) thành \(4\): \([1,4,2,2,1]\).
• \([1,4]\): \(\{1,4,2\}\) → 3 khác nhau. (Sửa ví dụ: đúng \(\{1,4,2,2\}\) → 3)
• \([3,5]\): \(\{2,2,1\}\) → 2 khác nhau.

Subtask