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:
The number of inversions in a sequence $$$a$$$ of length $$$n$$$ is the number of ordered pairs $$$(i,j)$$$ such that $$$1\leq i \lt j\leq n$$$, $$$a_j \lt 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
