Giải mã không bao giờ là một công việc đơn giản. Mỗi quốc gia đều có có thư viện riêng lưu trữ
hồ sơ các mật mã: Cách mã hóa và giải mã, Ai đã sử dụng nó và khi nào, . . . Với một thông tin
được mã hóa, việc đầu tiên người ta phải xác định một số đặc trưng để làm khóa tra cứu, tìm kiếm
trong thư viện.

Bài tập cho các học viên hôm nay là cho thông tin được mã hóa thành dãy số nguyên \(a_1, a_2, . . .,a_n\). Giả thiết \(a_1\) gặp trong dãy số \(k_1\) lần, \(a_2\) – gặp \(k_2\) lần, . . .Tính đồng nhất của dãy là số nguyên nhỏ nhất \(c \geq 1\) và \(c \neq k_i\) với mọi \(i\).

Yêu cầu xử lý \(q\) truy vấn, mỗi truy vấn thuộc một trong 2 dạng:

• \(1\ lf\ rt\) – Tìm tính đồng nhất dãy đã cho trong đoạn từ vị trí \(lf\) đến vị trí \(rt\) (kể cả \(rt\)), \(1 \leq lf \leq rt \leq n\),
• \(2\ p\ x\) – thay \(a_p\) bằng \(x\).

Với các truy vấn dạng 1 hãy đưa ra tính đồng nhất tìm được.

Input

• Dòng đầu tiên chứa 2 số nguyên \(n\) và \(q\) (\(1 \leq n, q \leq 10^5\)),
• Dòng thứ 2 chứa \(n\) số nguyên \(a_1, a_2, . . ., a_n\) (\(1 \leq a_i \leq 10^9, i = 1 ÷ n\)),
• Mỗi dòng trong \(q\) dòng sau chứa 3 số nguyên xác định một truy vấn.

Output

• Đưa ra kết quả tìm được ứng với truy vấn loại 1, mỗi
  kết quả trên một dòng.

Example

10 5
1 2 3 1 1 2 2 2 9 9
1 1 1
1 2 8
2 7 1
2 8 5
1 2 8

2
3
4