Prefix Count for Book Titles

You are given a collection of book titles and a set of query prefixes. For each query, your task is to count how many book titles start with the given prefix. A title is considered a match if the query string is a prefix of the title.

Input Format: The first line contains two space-separated integers (n) and (m), representing the number of book titles and the number of queries respectively. The next (n) lines each contain a single book title. The following (m) lines each contain a query prefix.

Output Format: Print (m) lines. The (i)-th line should contain the count of book titles that start with the (i)-th query prefix.

Constraints:

• \(0 \le n, m \le 10^5\)
• Each book title and query consists of lowercase English letters.

Note: For efficient queries, consider sorting the list of books and applying binary search techniques.

inputFormat

The first line contains two space-separated integers (n) and (m) — the number of book titles and queries. The next (n) lines each contain a book title. The following (m) lines each contain a query prefix.

outputFormat

Print (m) lines. The (i)-th line should contain a single integer, representing the number of book titles that start with the (i)-th query prefix.## sample

5 3
algorithm
algebra
geometry
geometric
altruism
al
geo
math

3
2
0