Game of Life

XDD is a game enthusiast who is addicted to games all day long. To save him from his addiction, his father decided to teach him some knowledge by designing a game.

One day, XDD's father designed the following game.

Given $N$ strings consisting of lowercase letters, followed by $Q$ queries. Each query consists of two strings $s_1$ and $s_2$. For each query, find the $K$-th smallest cost in the process of the two strings "meeting".

The definition of "meeting" is as follows: Suppose the longest common prefix of two strings $s_1$ and $s_2$ is $T$. Then, repeatedly remove one character from the end of $s_1$ and $s_2$ respectively until both strings are equal to $T$. The cost of removing a character $c$ from the end of a string is $\text{pow}(c, \text{num}[c]) \pmod{100007}$, where $c$ is the result of the character minus 'a' plus 1, and $\text{num}[c]$ is the number of occurrences of this character in the entire current string.

For example, if the two strings are "aabbcc" and "aabddd", the sequence of costs for them to meet is: aabbcc -> aabbc (cost $3^3=27 \pmod{100007} = 27$, note: the example in the problem description uses $3*3=9$, please follow the formula $\text{pow}(c, \text{num}[c]) \pmod{100007}$) -> aabb (cost $3^1=3$) -> aab (cost $2^1=2$) aabddd -> aabdd (cost $4^3=64$) -> aabd (cost $4^2=16$) -> aab (cost $4^1=4$) The costs in ascending order are: 2, 3, 4, 16, 27, 64.

Input

The first line contains $N$ and $Q$. The next $N$ lines each contain a string, representing $s[i]$. Then $Q$ lines follow, each containing three integers $x, y, k$, representing a query for the $k$-th smallest cost for the $x$-th string and the $y$-th string to meet. If the $k$-th smallest cost does not exist, output -1.

Output

For each query, output one integer representing the answer.

Examples

Input 1

5 5
oooono
ooono
oono
ono
no
1 2 5
2 3 4
3 4 3
4 5 2
1 5 4

Output 1

59326
3375
225
14
15

Constraints