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.

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 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

The next N lines contain the words s_i of the Old Barabarian language, consisting of lowercase Latin letters (1 ≤ |s_i| ≤ 10⁵).

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 ≤ u_i,v_i ≤ N, 0 ≤ c_i < \min(|s_ui|, |s_vi|)).

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

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⁻⁶. Formally, let your answer be x, and the jury’s answer be y. Your answer is considered correct if |x−y| / max(1,|y|) ≤ 10⁻⁶.