Cho ~n~ xâu kí tự và ~1~ xâu ~S~, ký tự thứ ~i~ được ký hiệu là ~S_i~ (~1\leq i\leq n~).

Có ~q~ thao tác được thực hiện trên ~S~, mỗi thao tác có dạng:

• ~(x,c)~: biến đổi tất cả kí tự của xâu ~S~ từ vị trí thứ ~x~ trở đi trở thành kí tự ~c~ (thực hiện phép gán ~S_i = c~ với mọi ~x\leq i\leq n~).

Yêu cầu

Sau mỗi thao tác, hãy in ra số lượng xâu trong mảng có thứ tự từ điển nhỏ hẳn hơn xâu ~S~.

Dữ liệu

• Dòng đầu tiên gồm hai giá trị ~n~ và ~q \ (1 \leq n, q \leq 10^6)~.
• Dòng thứ hai là xâu ~S~ với tối đa ~10^6~ ký tự là chữ cái Latin viết thường.
• ~n~ dòng tiếp theo là các xâu kí tự trong mảng, mỗi xâu chỉ chứa chữ cái Latin viết thường và tổng độ dài các xâu không vượt quá ~10^6~.
• ~q~ dòng cuối cùng là các truy vấn thay đổi dưới dạng ~(x,c)~ với ~x~ là 1 số nguyên dương (~1\leq x\leq n~) và ~c~ là 1 kí tự Latin viết thường, phân biệt bằng dấu cách.

Kết quả

• Dòng đầu tiên in kết quả bài toán trước khi có các thao tác thay đổi.
• ~q~ dòng tiếp theo, in kết quả bài toán sau mỗi thao tác thay đổi.

Ví dụ

Sample Input

4 3
anatoly
boris
anatooo
anbbbbu
anba
5 o
3 b
7 x

Sample Output

0
0
2
3

Giải thích

Thao tác 1: ~S="anatooo"~.

Thao tác 2: ~S="anbbbbb"~.

Thao tác 3: ~S="anbbbbx"~.