Cho ~1~ xâu ~s~ độ dài ~n~ gồm các ký tự nằm trong ~x~ chữ cái latin đầu tiên. Đặt ~s(l,r)~ là substring (xâu con liên tiếp) từ ~l~ đến ~r~ của ~s~. Định nghĩa hàm ~f(s)~ như sau (~f(s)~ có thể nhận nhiều giá trị):

• Nếu ~n>1~, ~f(s)~ có thể bằng ~-f(s(1,i))+f(s(i+1,n))~ với ~1 \le i<n~ (~i~ có thể lựa chọn).</p>

• Nếu ~n=1~, ~f(s)=2^c~ với ~c~ là số thứ tự của chữ cái duy nhất trong ~s~ (các chữ cái từ a–z được đánh số từ ~0~–~25~).

Hãy xử lý ~q~ truy vấn có ~2~ dạng:

• ! ~p~ ~c~: thay đổi chữ cái thứ ~p~ trong ~s~ thành ~c~.

• ? ~l~ ~r~ ~T~: xác định xem ~f(s(l,r))~ có thể bằng ~T~ không (~T \in \mathbb{Z}~)?

Input

Dòng đầu tiên chứa ~3~ số nguyên dương ~n, q, x~.

Dòng thứ hai chứa xâu ~s~ độ dài ~n~.

~q~ dòng tiếp theo, mỗi dòng chứa ~1~ truy vấn thuộc ~1~ trong ~2~ loại.

Gọi ~L~ là ~\max(|T|)~ (giá trị tuyệt đối lớn nhất của ~T~) trong mọi truy vấn ?.

Dữ liệu đảm bảo:

• ~1 \le p \le n~, ~1 \le l \le r \le n~, 'a' ~\le c \le~ 'z' với mọi truy vấn.

• ~L \le 10^{12}~, ~x \le 26~ và ~n,q \le 10^5~.

• Xâu ~s~ chỉ gồm các ký tự nằm trong ~x~ chữ cái latin đầu tiên tại mọi thời điểm.

Output

Với mỗi truy vấn ?, in ra câu trả lời dưới dạng "YES/NO". Việc viết thường hay viết hoa các ký tự là không quan trọng.

Scoring

Sample Input 1

3 5 3
abc
! 1 c
? 1 2 -3
! 2 c
! 3 a
? 1 3 -7

Sample Output 1

NO
YES