Thống kê lượt theo tiền tố

Bối cảnh và bài toán

Một hệ thống tìm kiếm nội bộ lưu n từ khóa đã được ghi nhận. Bộ phận phân tích gửi nhiều tiền tố và cần biết có bao nhiêu từ khóa bắt đầu bằng từng tiền tố đó.

Yêu cầu

Với mỗi truy vấn tiền tố p, đếm số chuỗi trong tập dữ liệu bắt đầu bằng p.

Input

• Dòng 1 chứa n q.
• n dòng tiếp theo là các chuỗi dữ liệu.
• q dòng tiếp theo là các tiền tố cần hỏi.

Output

In một số nguyên cho mỗi truy vấn.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• Tổng độ dài mọi chuỗi và truy vấn không vượt 5 * 10^5.
• Chuỗi chỉ gồm a..z.

Chấm điểm

Ví dụ 1

Input

5 4
app
apple
ape
bat
batch
ap
app
b
cat

Output

3
2
2
0

Giải thích. Ba từ bắt đầu bằng ap; hai từ bắt đầu bằng app; không có từ bắt đầu bằng cat.

Ví dụ 2

Input

3 3
a
aa
aaa
a
aa
aaaa

Output

3
2
0

Giải thích. Các prefix dài hơn dần lọc bớt số từ phù hợp.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.