Cho một chuỗi ký tự ~s~ với độ dài ~n~ chỉ bao gồm các chữ cái tiếng Anh in thường. Cho ~q~ truy vấn gồm 2 loại như sau:

• ~1~ ~x~ ~y~: Đổi toàn bộ các ký tự ~x~ trong chuỗi ~s~ thành ký tự ~y~.
• ~2~ ~x~: Đưa ra số lần xuất hiện của ký tự ~x~ trong chuỗi ~s~.

Yêu cầu

Cho ~s~ và ~q~ truy vấn. Với mỗi truy vấn loại ~2~, in ra số lần xuất hiện của ký tự tương ứng.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~q~ ~(1≤n,q≤10^6)~ cách nhau một dấu cách.
• Dòng thứ hai chứa chuỗi ký tự ~s~.
• ~q~ dòng sau, mỗi dòng là một truy vấn có dạng ~1~ hoặc ~2~.

Output

Mỗi dòng tương ứng với kết quả của các truy vấn dạng ~2~.

Sample Input

5 7
abcda
2 a
1 a b
2 a
2 b
2 d
1 b d
2 d

Sample Output

2
0
3
1
4

Giải thích

Ban đầu chuỗi ký tự là ~abcde~.

Truy vấn 1 yêu cầu đưa ra số lần xuất hiện của ký tự ~a~, kết quả là ~2~ lần.

Truy vấn 2 yêu cầu đổi toàn bộ ký tự ~a~ thành ký tự ~b~, chuỗi chuyển thành ~bbcdb~.

Truy vấn 3, 4, 5 yêu cầu đưa ra số lần xuất hiện của ký tự ~a~, ~b~, ~d~, kết quả lần lượt là ~0~, ~3~ và ~1~ lần.

Truy vấn 6 yêu cầu đổi toàn bộ ký tự ~b~ thành ký tự ~d~, chuỗi chuyển thành ~ddcdd~.

Truy vấn 7 yêu cầu đưa ra số lần xuất hiện của ký tự ~d~, kết quả là ~4~ lần.

Subtask

• Có 50% số test ứng với 50% số điểm có ~1≤n,q≤10^3~;
• 50% số test còn lại tương ứng với 50% số điểm không có giới hạn gì thêm.