L. String Insertion
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a dictionary of $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$.

We define $$$f(t)$$$ as the number of ways of obtaining a string $$$t$$$ by the following three-step operation:

  1. Select two (not necessarily distinct) indices $$$i$$$ and $$$j$$$ from the dictionary.
  2. Select an integer $$$k$$$ such that $$$0 \leq k \leq |s_i|$$$. Let $$$a$$$ be the prefix of $$$s_i$$$ of length $$$k$$$, and let $$$b$$$ be the suffix of $$$s_i$$$ of length $$$|s_i|-k$$$. $$$a$$$ or $$$b$$$ may be empty.
  3. Concatenate the strings $$$a + s_j + b$$$. If this concatenation is equal to $$$t$$$, it counts as one valid way to obtain $$$t$$$.

Each valid triple $$$(i, j, k)$$$ is counted separately.

You are given $$$q$$$ strings $$$t_1, t_2, \dots, t_q$$$. For each $$$t_i$$$ ($$$1 \leq i \leq q$$$), find the value of $$$f(t_i)$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — the number of strings in the dictionary and the number of queries.

The following $$$n$$$ lines contain the strings $$$s_1, s_2, \dots, s_n$$$ in the dictionary.

The following $$$q$$$ lines contain the query strings $$$t_1, t_2, \dots, t_q$$$.

It is guaranteed that all strings in the input consist of lowercase English letters.

It is guaranteed that the total length of the strings $$$s_1, s_2, \dots, s_n$$$ does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the total length of the strings $$$t_1, t_2, \dots, t_q$$$ does not exceed $$$2 \cdot 10^5$$$.

Output

For each query string $$$t_i$$$, print a single line containing the value of $$$f(t_i)$$$.

Examples
Input
2 2
abab
ab
ababab
aabbab
Output
5
1
Input
2 1
abc
abc
abcabc
Output
8