Вадим решил покорять новые просторы и начать писать рэп на старобарском. В старобарском языке N слов, а в алфавите всего 26 букв, для своего удобства Вадим запоминает их как латинские. В этом языке произносится каждая буква слова, а, значит, и рифмуются слова гораздо проще.

Однако, чтобы посчитать, насколько хорошо рифмуются два слова, нужно нехило заморочиться. Вадим выбирает суффикс одинаковой длины у двух слов, и они рифмуются на значение, равное этой длине и делённое на 2 за каждое различие в каждой из соответствующих позиций. При этом Вадим может сам выбрать любую длину суффикса, поэтому два слова рифмуются на значение, максимальное для каждой пары суффиксов одинаковой длины.

Вадиму уже известны значения каждого из слов, поэтому осталось только написать текст в рифму. У него есть Q вариантов, подходящих по смыслу для его трека. Чтобы звучать более в рифму, Вадим даже готов отрезать по нескольку букв с конца у обоих слов. Помогите начинающему рэперу, ответив для каждого варианта, насколько хорошо получится рифма из этих двух слов.

В первой строке даны два целых числа N и Q — количество слов в старобарском языке и количество вариантов, предложенных Вадимом (2 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

В следующих N строках даны слова s_i старобарского языка, состоящие из строчных латинских букв (1 ≤ |s_i| ≤ 10⁵).

В следующих Q строках даны три целых числа u_i, v_i и c_i — два номера слов из старобарского языка в порядке ввода, которые содержатся в i-м варианте Вадима; и количество букв, которые он отрежет с конца у обоих слов (1 ≤ u_i,v_i ≤ N, 0 ≤ c_i < \min(|s_ui|, |s_vi|)).

Гарантируется, что общая длина всех слов не превосходит 10⁶ символов.

Выведите Q чисел — насколько хороша рифма для каждого из вариантов в порядке ввода.

Ответ будет засчитан, если абсолютная или относительная погрешность значений не превосходит 10⁻⁶. Формально, пусть ваш ответ равен x, а ответ жюри равен y. Ваш ответ считается правильным, если |x−y| / max(1,|y|) ≤ 10⁻⁶.