Background

Luogu’s testdata is only for non-official community use and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

Xixi Aifu Island Travel Company has recently launched a series of shining cruise routes around Xixi Aifu Island. Ordinary routes are usually loops, so that passengers can return to the starting point after a long journey; while shining routes are mostly one-way routes with some thrills but no real danger. Therefore, Xixi Aifu Island Travel Company also allows passengers to choose combinations of routes that can return to the starting point.

Specifically, each route provided by the company can be represented by a string containing only lowercase letters, where each letter represents a destination visited along the route. For example, the route aqua represents a route that starts from a, passes through q and u, and finally returns to a. The company currently operates $N$ such routes, denoted by strings $s_1, s_2, \cdots, s_N$. We define the length of a route as the length of its string minus $1$; for example, the route aqua has length $3$.

To encourage passengers to take its cruises, the company has launched a stamp-collecting activity. When taking a cruise and passing through certain destinations (which can be the starting point or the ending point of the taken route), passengers can obtain a stamp. We use a string $t$ to represent all destinations participating in the stamp-collecting activity. When a passenger collects all stamps corresponding to all letters in $t$, they have a chance to win prizes such as free stays in luxury hotels.

To determine the expected profit brought by the stamp-collecting activity, the company wants to know: for each route $s_i$, starting from the starting point of $s_i$, take $s_i$ to reach the ending point of $s_i$, then take several more routes (possibly $0$ routes) to finish collecting all stamps and return to the starting point of $s_i$, what is the minimum total length of the route combination that needs to be taken.

Input Format

Read from standard input.

The first line contains a positive integer $N$ and a string $t$, with $1 \le N \le 10^5$, $1 \le |t| \le 10$, and $t$ containing only distinct lowercase letters.

The next $N$ lines each contain a string $s_i$, representing the $i$-th route. It is guaranteed that $2 \le |s_i| \le 10^6$, and $\sum_{i=1}^{N} |s_i| \le 10^6$.

Output Format

Write to standard output.

Output $N$ lines. Each line outputs a positive integer representing the minimum total length of the corresponding route combination, or output -1 if no route combination satisfies the requirement.

6 au
aqua
glass
hug
shiny
sparkling
youth

3
14
14
14
26
14

7 i
nonstop
perfect
rocket
thrilling
train
trapper
tripper

16
16
11
-1
16
22
11

Hint

Subtasks

• For $10\%$ of the data, it is guaranteed that $1 \le N \le 10$, $1 \le |t| \le 5$.
• For another $10\%$ of the data, it is guaranteed that $1 \le N \le 1000$, $|t| = 1$.
• For another $20\%$ of the data, it is guaranteed that $1 \le |t| \le 5$.
• For $100\%$ of the data, it is guaranteed that $1 \le N \le 10^5$, $1 \le |t| \le 10$, $2 \le |s_i| \le 10^6$, $\sum_{i=1}^{N} |s_i| \le 10^6$, $s_i$ and $t$ contain only lowercase letters, and the letters in $t$ are distinct.

Translated by ChatGPT 5