Cho xâu ~s~ độ dài ~n~ chỉ chứa các ký tự chữ cái in thường từ a đến z. Thực hiện ~q~ truy vấn thuộc một trong hai loại sau:

• Loại ~1~ có dạng 1 i c ~(1 \le i \le n~ ~;~ ~c~ là ký tự chữ cái in thường~)~: Gán ~s_i=c~.
• Loại ~2~ có dạng 2 l r ~(1 \le l \le r \le n)~: Đếm số lượng ký tự phân biệt trong xâu con ~s_ls_{l+1}...s_r~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 5 \times 10^5)~.
• Dòng thứ hai chứa xâu ~s~ độ dài ~n~.
• Dòng thứ ba chứa số nguyên ~q~ ~(1 \le q \le 2 \times 10^4)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại trên.

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả trên một dòng.

Examples

Sample Input 1

5
abcde
5
2 1 5
1 3 a
2 1 3
1 5 b
2 2 5

Sample Output 1

5
2
3

Sample Input 2

10
aaaaaaaaaa
3
2 1 10
1 5 z
2 5 5

Sample Output 2

1
1