背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

西西艾弗岛旅游公司最近推出了一系列环绕西西艾弗岛的闪耀游轮航线。普通的航线通常是一条环线，以便乘客在漫长的旅途之后回到出发点；而闪耀航线则多为有惊无险的单程。因此，西西艾弗岛旅游公司也允许乘客自己选择一些能够返回起点的航线组合。具体而言，西西艾弗岛旅游公司推出的航线可以用仅包含小写字母的字符串表示，其中每一种字母代表航线中途经的一个目的地。例如，航线 aqua 表示从 a 出发，途经 q 和 u，最终返回 a 的航线。西西艾弗岛旅游公司目前运营着 $N$ 条这样的航线，分别用字符串 $s_1, s_2, \cdots, s_N$ 表示。我们定义，一条航线的长度为相应的字符串长度减 $1$，如航线 aqua 的长度为 $3$。

西西艾弗岛旅游公司为了鼓励乘客乘坐其游轮，推出了一项集章活动。乘坐其游轮途经部分目的地（可以是搭乘的航线的起点或终点）时，可以获得一枚印章。我们用字符串 $t$ 表示所有参与集章活动的目的地。当乘客集齐 $t$ 中所有字母对应的印章时，有机会抽取免费住宿豪华酒店等幸运大奖。

为了确定集章活动给公司带来的预期利润，西西艾弗岛旅游公司想知道：对于每条航线 $s_i$，从 $s_i$ 的起点出发搭乘 $s_i$ 到达 $s_i$ 的终点，再经过多条航线（可以是 $0$ 条）完成集章后返回 $s_i$ 的起点，需要乘坐的航线组合的最小总长度。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $N$ 和一个字符串 $t$，保证 $1 \le N \le 10^5$，$1 \le |t| \le 10$，且 $t$ 仅包含不重复的小写字母。

接下来 $N$ 行，每行包含一个字符串 $s_i$，表示第 $i$ 条航线。保证 $2 \le |s_i| \le 10^6$，$\sum_{i=1}^{N} |s_i| \le 10^6$。

输出格式

输出到标准输出。

输出包含 $N$ 行，每行输出一个正整数表示对应航线组合的最小总长度，或者输出 -1 表示不存在满足要求的航线组合。

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

提示

子任务

• 对于 $10\%$ 的数据，保证 $1 \le N \le 10$，$1 \le |t| \le 5$。
• 对于另外 $10\%$ 的数据，保证 $1 \le N \le 1000$，$|t| = 1$。
• 对于另外 $20\%$ 的数据，保证 $1 \le |t| \le 5$。
• 对于 $100\%$ 的数据，保证 $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$ 和 $t$ 仅包含小写字母，且 $t$ 中字母不重复。