题目背景

题目描述

摸鱼酱声称自己既是字符串领域大神，又是数据结构领域大神，因为他不仅会使用后缀数组来给字符串排序，还会使用树状数组来求序列的逆序对。

于是教练决定把这两个问题揉在一起来考考摸鱼酱。具体而言，教练会给出一个长度为 $n$ 的序列，序列中每个元素都是一个小写字母组成的字符串；然后教练还会给出 $q$ 张字母表，是传统字母表 $abc...xyz$ 的一个打乱的排列，问他按照每张字母表的排序规则下，给出的序列分别有多少个逆序对。

序列 $a$ 中的 $(i,j)$ 是逆序对当且仅当 $a_i>a_j$，其中 $i < j$。

字符串 $s < t$ 当且仅当：$s$ 是 $t$ 的前缀并且 $s\neq t$；或者存在一个整数 $k$，$s[1...k]=t[1...k]$，而 $s[k+1]$ 在字母表中比 $t[k+1]$ 出现在更前的位置。

输入格式

第一行输入两个整数 $n,q$。

接下来的 $n$ 行，第 $i$ 输入一个字符串 $s_i$ 表示序列的第 $i$ 个字符串，由小写字母组成。

接下来的 $q$ 行，每行输入一个长度为 $26$ 的字符串，表示一张打乱的字母表。

输出格式

对于每张字母表，输入按照其排序规则下序列的逆序对数量。

输入样例

5 3
aac
oiputata
aaa
suikabudada
aba
abcdefghijklmnopqrstuvwxyz
qwertyuiopasdfghjklzxcvbnm
aquickbrownfxjmpsvethlzydg

输出样例

4
3
4

说明提示

【数据范围与提示】

对于 $30\%$ 的数据，$n\leq 100,q\leq 100,|s_i|\leq 100$。

对于 $50\%$ 的数据，$n\leq 1000,q\leq 1000$。

对于另外 $10\%$ 的数据，$q=1$，字母表是没有打乱的，即 $abc...xyz$。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5,1\leq q\leq 5\times 10^4,\sum|s_i|\leq 10^6+5$，保证输入的字母表是 $a...z$ 的一个排列。

本站补充：原套别：第 14 套 C 题。