410722: GYM104090 K Master of Both

Professor Hui-Bot is the master of string theory and advanced data structures, so he came up with an interesting problem. Given a sequence of $$$n$$$ strings consisting of only lowercase English letters, how many inversions are there in this sequence when the strings are compared by lexicographical order?

As the most extraordinary student of Hui-Bot, Putata and Budada mastered superb string theory and advanced data structure skills respectively, and they solved this problem together with ease. However, there are $$$q$$$ different parallel universes, where the characters in the alphabet are not appearing in the original order.

Formally, the alphabet in each universe is a string, which is a permutation of the $$$26$$$ lowercase English letter, denoting the order each character appears.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

• $$$a$$$ is a prefix of $$$b$$$, but $$$a\neq b$$$;
• in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

The number of inversions in a sequence $$$a$$$ of length $$$n$$$ is the number of ordered pairs $$$(i,j)$$$ such that $$$1\leq i<j\leq n$$$, $$$a_j<a_i$$$.

Please help Putata and Budada in each universe to solve the problem.

The first line of the input contains two integers $$$n,q$$$ ($$$1\leq n\leq 5\times 10^5$$$, $$$1\leq q\leq 5\times 10^4$$$), denoting the length of the sequence.

For the following $$$n$$$ lines, the $$$i$$$-th line contains a string $$$s_i$$$ ($$$1\leq |s_i|\leq 10^6$$$). It is guaranteed that the string consists of only lowercase English letters, and $$$\sum\limits_{i=1}^n |s_i|\leq 10^6$$$.

For the following $$$q$$$ lines, each line contains a string $$$t$$$, denoting the alphabet in one universe. It is guaranteed that $$$t$$$ is a permutation of $$$26$$$ lowercase English letters.

Output $$$q$$$ lines, denoting the answer in $$$q$$$ universes.

5 3
aac
oiputata
aaa
suikabudada
aba
abcdefghijklmnopqrstuvwxyz
qwertyuiopasdfghjklzxcvbnm
aquickbrownfxjmpsvethlzydg

4
3
4