Trong tiết tin học ngày hôm nay, thầy giáo của bạn đã tổ chức một trò chơi rất vui nhộn.

Nội dung của trò chơi như sau: Cho ~n~ chuỗi ký tự. Thực hiện ~q~ thao tác xoá, mỗi thao tác cho một ký tự ~c~, yêu cầu xoá tất cả các chuỗi ký tự có chứa ký tự ~c~ và in ra số lượng chuỗi kí tự còn lại sau mỗi thao tác.

Nếu trả lời đúng, thầy sẽ khao cả lớp một bữa ăn buffet rất hoành tráng. Bạn là trùm tin học của lớp nên các bạn cùng lớp của bạn rất tin tưởng vào bạn.

Hãy lập trình giải bài toán trên để nhận được phần thưởng của thầy nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q;~
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu ký tự gồm chữ cái in thường, độ dài không quá ~10;~
• ~q~ dòng sau, mỗi dòng chứa một ký tự chữ cái in thường mô tả thao tác xoá.

Output

In ra ~q~ dòng tương ứng với kết quả sau mỗi thao tác.

Scoring

• Subtask 1 [50%]: ~n, q \le 100;~
• Subtask 2 [50%]: ~n, q \le 10^5;~

Examples

Input

4 3
hnoj
vnoi
codeforces
hackerearth
n
h
o

Output

2
1
0