Cho ~n~ xâu ~s_1, s_2, s_3, \dots, s_n~ khác rỗng. Mỗi xâu chỉ gồm các chữ cái tiếng Anh in thường từ a đến z. Các xâu trong danh sách có thể giống nhau.

Có ~q~ truy vấn, mỗi truy vấn gồm một xâu ~p~ khác rỗng và một số nguyên dương ~k~, xét tất cả các xâu ~s_i~ thỏa mãn:

• ~p~ là tiền tố của ~s_i~, một xâu được coi là tiền tố của chính nó;

• ~|s_i| \ge k~.

Từ mỗi xâu thỏa mãn, lấy đúng ~k~ ký tự cuối và đếm số lượng hậu tố phân biệt thu được.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, q~ ~(1 \le n, q \le 2 \cdot 10^5)~;

• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa xâu ~s_i~ (tổng độ dài của tất cả các xâu ~s_i~ không vượt quá ~5 \cdot 10^5~);

• Trong ~q~ dòng tiếp theo, dòng thứ ~j~ chứa xâu ~p_j~ (tổng độ dài của tất cả các xâu ~p_j~ không vượt quá ~5 \cdot 10^5~) và số nguyên ~k_j~ ~(1 \le k_j \le 5 \cdot 10^5)~.

Output

Gồm ~q~ dòng tương ứng với kết quả mỗi truy vấn là số lượng hậu tố phân biệt thu được.

Scoring

Sample Input 1

6 6
abc
axbc
abca
abbc
bc
abc
a 2
ab 1
abc 3
b 2
z 1
a 5

Sample Output 1

2
2
2
1
0
0

Notes

• Với truy vấn a ~2~, có năm xâu phù hợp tạo ra các hậu tố bc, bc, ca, bc, bc. Có hai hậu tố phân biệt là bc và ca nên đáp án bằng ~2~.

• Với truy vấn abc ~3~, có ba xâu phù hợp tạo ra các hậu tố abc, bca, abc. Có hai hậu tố phân biệt là abc và bca nên đáp án bằng ~2~.

• Với truy vấn z ~1~, không có xâu nào bắt đầu bằng z nên đáp án bằng ~0~.

• Với truy vấn a ~5~, không có xâu bắt đầu bằng a và dài ít nhất ~5~ nên đáp án bằng ~0~.