Problem E
The Point of No Return

Twilight Sparkle forgot to return a book to the Canterlot Library, and it’s been two years—eight seasons—since she borrowed it! As a consequence, not only has she lost her perfect library book return record, she’s also had to pay a fine of twenty-eight bits; and, possibly worst of all, she now needs to perform library service to restore her good standing with the library.

Figure 1: Illustration by Kyle Coate.

One of the things Twilight has to accomplish is to arrange the books in one section of the library by title. There are $N$ books in this section of the library, placed neatly on a bookshelf. The title of the $i^\text {th}$ book from the left is $T_ i$; every title is a non-empty string of lowercase and uppercase Latin alphabet characters and spaces which does not contain two consecutive spaces and whose first and last characters are not spaces.

Twilight will perform the following simple process to arrange these books:

1. She keeps track of two positions $i$ and $j$.

2. First, she sets the value of $i$ to $1$.

3. Then, she repeats the following process until $i = N-1$:

   1. She sets the value of $j$ to $i+1$.

   2. Then, she repeats the following process until $j = N$:

      1. Compare the titles of the $i^\text {th}$ and $j^\text {th}$ books. If $T_ j$ is lexicographically smaller than $T_ i$, then swap these two books. Regardless of whether the books are swapped or not, this takes $1$ second.

      2. Move $j$ to the right once, so that the value of $j$ is now $j+1$.

   3. Move $i$ to the right once, so that the value of $i$ is now $i+1$.

It can be shown that, after Twilight finishes this process, the books will definitely be arranged in the correct order.

A title $t$ is lexicographically smaller than another title $t’$ if and only if, when we treat lowercase and uppercase Latin alphabet characters as the same character, either

1. $t’ = ta$ for some non-empty string $a$, or

2. $t = sa$ and $t’ = sb$ for some possibly empty string $s$ and non-empty strings $a, b$, where

   1. the first character of $a$ is a space and the first character of $b$ is not a space, or

   2. the first character of $a$ is not a space and the first character of $b$ is not a space and the first character of $a$ comes strictly before the first character of $b$ in the alphabet.

For simplicity, assume that for any two books $i$ and $j$ with $i \neq j$ in the library, either $T_ i$ is lexicographically smaller than $T_ j$ or $T_ j$ is lexicographically smaller than $T_ i$.

Ponies do not exactly have opposable thumbs, and so every time Twilight has to swap two books, she uses her magic and afterwards her level of fatigue increases by one. She does not want to get too fatigued and needs to know when to schedule her breaks. She hence asks $Q$ independent questions. In the $i^\text {th}$ question, she wants to know how many seconds it will take until she first reaches a level of fatigue $F_ i$. Note that it may be possible that she can never reach that level of fatigue, in which case you must also tell her that.

Help her answer her questions, and restore her good standing with the Canterlot Library!

Input

The first line of input contains two integers, $N$ ($2 \leq N \leq 200\, 000$) and $Q$ ($1 \leq Q \leq 200\, 000$), the number of books on the bookshelf and the number of questions Twilight wants to ask, respectively.

The next $N$ lines of input contain the descriptions of the books on the bookshelf. In particular, the $i^\text {th}$ of these lines contains a string $T_ i$ ($1 \leq |T_ i| \leq 35$), denoting the title of the $i^\text {th}$ book from the left.

The next $Q$ lines of input contain the descriptions of the questions Twilight asks. In particular, the $i^\text {th}$ of these lines contains a single integer $F_ i$ ($1\leq F_ i \leq 10^{12}$), denoting that she wants to know how many seconds it will take until she first reaches a level of fatigue $F_ i$.

It is guaranteed that $T_ i$ contains only lowercase and uppercase Latin alphabet characters and spaces, does not contain two consecutive spaces and its first and last characters are not spaces.

It is also guaranteed that either $T_ i$ is lexicographically smaller than $T_ j$ or $T_ j$ is lexicographically smaller than $T_ i$ for $i \neq j$.

Output

Output $Q$ lines, the answers to Twilight’s questions. In particular, the $i^\text {th}$ of these lines should contain either the string IMPOSSIBLE, if Twilight will never reach a level of fatigue $F_ i$, or a single integer denoting the time in seconds it will take for her to reach that level of fatigue, otherwise.

6 8
Daring Do and the Ring of Destiny
Perfection The Impossible Pursuit
Gusty the Great
Understanding Medieval Equestria
Daring Do and the Razor of Dreams
Me and My Shadow
1
2
3
4
5
6
7
8

4
6
8
11
13
14
15
IMPOSSIBLE