小柒的逆序对（二）

题号：NC288864
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小柒是一名科学家，最近他发现了平行宇宙的存在，并且在每个平行宇宙中，字典序是不一样的。
$\hspace{15pt}$ 也就是说在某个平行宇宙，字母表的出现顺序也许是 $\texttt{`a'} > \texttt{`b'} > \texttt{`c'} > \cdots$ ，但是在另一个平行宇宙中，字母表的出现顺序是 $\texttt{`c'} > \texttt{`b'} > \texttt{`a'} > \cdots$ ，那么 $\texttt{`c'}$ 的字典序就会小于 $\texttt{`a'}$ 。
$\hspace{15pt}$ 小柒将会给你一个字符串 $s$ ，并且给你 $q$ 个平行宇宙中的字母表。他想知道在不同的平行宇宙中，这个字符串 $s$ 分别拥有多少个逆序对。

$\hspace{15pt}$ 在字符串中，若存在这样的两个下标 $i,j$ 满足 $i<j$ ，且其对应的字符 $a_i$ 在当前字母表中出现的顺序晚于 $a_j$ ，则称 $i$ 与 $j$ 构成一个逆序对。

输入描述:

第一行输入两个整数  代表字符串  的长度、平行宇宙的数量。 
第二行输入一个长度为 ，仅由小写字母组成的字符串 。 
此后  行，每行输入一个长度为 ，由小写字母组成、且每个字母只出现一次的字符串，代表每个宇宙的字母表。

输出描述:

对于每一个宇宙，新起一行输出一个整数，代表在当前宇宙中，字符串  拥有的逆序对数量。

示例1

输入

复制

20 5
sdsasaknsdialpanaonc
abcdefghijklmnopqrstuvwxyz
krsotmdezblqwujfxhcvyagpin
iegkywuvdpboaltrjhsmncqfxz
evzjpqftrihdolynuxkwbamcgs
sczrmwupjxoaiekghfvtybqldn

输出

复制