K. Old Barabarian Rap
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vadim decided to conquer new horizons and start writing rap in Old Barabarian. The Old Barabarian language has $$$N$$$ words, and its alphabet consists of only $$$26$$$ letters, which Vadim conveniently remembers as Latin letters. In this language, each letter of a word is pronounced, and thus, rhyming words is much simpler.

However, to calculate how well two words rhyme, one needs to put in some effort. Vadim chooses a suffix of the same length from the two words, and they rhyme with a value equal to this length divided by $$$2$$$ for each difference in the corresponding positions. Moreover, Vadim can choose any length of the suffix, so two words rhyme with the maximum value for each pair of suffixes of the same length.

Vadim already knows the meanings of each of the words, so he just needs to write the text in rhyme. He has $$$Q$$$ options that fit the meaning for his track. To sound more in rhyme, Vadim is even willing to cut a few letters from the end of both words. Help the aspiring rapper by answering for each option how well the rhyme will turn out from these two words.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ — the number of words in the Old Barabarian language and the number of options proposed by Vadim $$$(2 \le N \le 10^5, 1 \le Q \le 10^5)$$$.

The next $$$N$$$ lines contain the words $$$s_i$$$ of the Old Barabarian language, consisting of lowercase Latin letters $$$(1 \le |s_i| \le 10^5)$$$.

The following $$$Q$$$ lines contain three integers $$$u_i$$$, $$$v_i$$$, and $$$c_i$$$ — two indices of words from the Old Barabarian language in the order of input that are contained in the $$$i$$$-th option of Vadim; and the number of letters he will cut from the end of both words $$$(1 \le u_i,v_i \le N, 0 \le c_i \lt \min(|s_{u_i}|, |s_{v_i}|))$$$.

It is guaranteed that the total length of all words does not exceed $$$10^6$$$ characters.

Output

Output $$$Q$$$ numbers—how good the rhyme is for each option in the order of input.

The answer will be accepted if the absolute or relative error of the values does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$x$$$, and the jury's answer be $$$y$$$. Your answer is considered correct if $$$\frac{|x-y|}{\max (1,|y|)} \le 10^{-6}$$$.

Example
Input
5 7
fate
cmake
stake
cfake
cmate
1 2 0
2 3 0
1 4 0
2 5 0
1 5 0
1 4 1
2 5 2
Output
1.5
3
2
2.5
3
1.5
3