Naum's cellphone has a keypad just like on the image below. When he's typing someone's name, Naum needs to press just once the key that contains the letter which he's typing at the moment.
Everyone was very impressed by this amazing functionality, except for you. So, Naum challenged you to solve this problem, if you really want to prove that this functionality isn't that awesome after all.
Given a list of $N$ Naum's cellphone contacts and $Q$ sequences of pressed keys, you must answer, for each sequence, the number of contacts whose name could actually be being typed by Naum.
Formally, Naum could be typing a name $s$ with the sequence of letters $t$ if there is a replacement of the keys in $t$ for the letters they represent, resulting in string $t '$, where $t '$ is a prefix of $s$.
The first line of input contains two integers $N$ and $Q$ ($1 <= N <= 10^5$, $1 <= Q <= 2 dot.op 10^5$), being the size of Naum's cellphone contact list and the number of sequences to be analyzed, respectively.
Then, $N$ lines follow, where the $i$-th of them contain a string $s_i$ $(0 < s_i <= 10^5)$, the name of the $i$-th contact, which consists only in lowercase english letters, from A to Z.
Finally, $Q$ lines follow, where the $i$-th of them contains a string $t_i$ ($0 < t_i <= 10^5$), the $i$-th sequence of keys typed by Naum, which consists of numbers from $0$ to $9$ (inclusive).
It is guaranteed that $sum_{i = 1}^N | s_i | <= 10^6$ and $sum_{i = 1}^Q | t_i | <= 10^6$.
You must output $Q$ integers, the answer for each one of the given sequences of keys.
## Input
The first line of input contains two integers $N$ and $Q$ ($1 <= N <= 10^5$, $1 <= Q <= 2 dot.op 10^5$), being the size of Naum's cellphone contact list and the number of sequences to be analyzed, respectively.Then, $N$ lines follow, where the $i$-th of them contain a string $s_i$ $(0 < s_i <= 10^5)$, the name of the $i$-th contact, which consists only in lowercase english letters, from A to Z.Finally, $Q$ lines follow, where the $i$-th of them contains a string $t_i$ ($0 < t_i <= 10^5$), the $i$-th sequence of keys typed by Naum, which consists of numbers from $0$ to $9$ (inclusive).It is guaranteed that $sum_{i = 1}^N | s_i | <= 10^6$ and $sum_{i = 1}^Q | t_i | <= 10^6$.
## Output
You must output $Q$ integers, the answer for each one of the given sequences of keys.
[samples]
**Definitions**
Let $ a, b, r, d \in \mathbb{R}^+ $ be given:
- $ a $: width of the car (in inches)
- $ b $: length of the car (in inches)
- $ r $: radius of the circular arc (internal boundary)
- $ d $: central angle of the arc in degrees
Let $ \theta = \frac{d \pi}{180} $ be the central angle in radians.
The car is modeled as a rectangle of width $ a $ and length $ b $, with its right front corner tracing the arc of radius $ r $. The car's orientation is always tangential to the arc.
**Constraints**
$ 0 < a, b, r < 100 $, $ 0 < d < 180 $
**Objective**
Compute the minimal lane width $ w $ such that the entire car remains within the lane during the turn.
The outer boundary of the lane is the locus of the farthest point of the car from the center of the arc. The farthest point is the **left rear corner** of the car.
Let $ O $ be the center of the circular arc.
At any instant, the right front corner $ P $ lies on the arc of radius $ r $.
The car’s orientation is tangential to the arc at $ P $.
The vector from $ P $ to the left rear corner $ Q $ is:
- $ -a $ units perpendicular to the tangent (leftward, normal direction),
- $ -b $ units opposite to the tangent direction (backward).
Thus, the distance from $ O $ to $ Q $ is:
$$
\| \vec{OQ} \| = \sqrt{ (r - a)^2 + b^2 }
$$
The minimal lane width $ w $ is the difference between the maximum distance from $ O $ to any point on the car and the radius $ r $:
$$
w = \sqrt{(r - a)^2 + b^2} - r
$$
**Output**
For each test case, output $ w = \sqrt{(r - a)^2 + b^2} - r $