Cho xâu \(S\) độ dài \(N\) chỉ chứa các chữ cái latin in thường, các ký tự được đánh chỉ số từ \(1\). Hãy lập trình xử lý lần lượt \(Q\) truy vấn ở hai loại sau:

• Loại \(1\): Thay đổi ký tự thứ \(i\) của \(S\) thành \(c\) (không làm gì cả nếu \(S_i=c\) sẵn).
• Loại \(2\): Đếm số lượng ký tự phân biệt xuất hiện trong xâu con từ vị trí \(l\) đến vị trí \(r\) của \(S\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \((N\leq 5\cdot 10^5)\).
• Dòng tiếp theo chứa xâu \(S\) bao gồm \(N\) ký tự latin in thường.
• Dòng tiếp theo chứa số nguyên dương \(Q\) \((Q\leq 2\cdot 10^4)\).
• \(Q\) dòng tiếp theo có dạng 1 i c hoặc 2 l r thể hiện một truy vấn ở thể loại tương ứng.

Output

• Với mỗi truy vấn loại \(2\), in ra số lượng ký tự phân biệt cần tìm.

Example

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

3
1
5