Сколько прочтёт Хорспул

Прежде чем ставить алгоритм поиска в свою программу, хочется знать, сколько работы он сделает на ваших данных, а не на чужом замере. Посчитайте это для алгоритма Хорспула — упрощённого Бойера — Мура, на котором держатся быстрые поиски в стандартных библиотеках.

Текст t длины n, образец p длины m. Окно — место, куда приложен образец; первое окно начинается в позиции 0. В окне с началом s алгоритм сравнивает p[m − 1] с t[s + m − 1], потом p[m − 2] с t[s + m − 2] и так справа налево, пока буквы равны; каждая проверка пары букв — одно сравнение. Если совпали все m букв, это вхождение. Потом, совпало или нет, окно сдвигается на d(c), где c = t[s + m − 1] — буква текста под последней клеткой окна:

• если c встречается среди первых m − 1 букв образца, d(c) = m − 1 − j, где j — самая правая такая позиция;
• если не встречается, d(c) = m.

Алгоритм останавливается, когда окно перестаёт помещаться в текст. Для каждого образца выведите, сколько окон он проверил, сколько сделал сравнений и сколько нашёл вхождений. Среди тестов — начало «Войны и мира» и перевода Мод, геном фага лямбда и пример из статьи Мура «HERE IS A SIMPLE EXAMPLE».

Вход

В первой строке — текст, от 1 до 100 000 знаков (UTF-8, без переводов строки; пробелы — обычные знаки). Во второй — число образцов q (1 ≤ q ≤ 20). В каждой из следующих q строк — образец, от 1 до 100 знаков. Позиции считаются в знаках, а не в байтах. Тесты такие, что на каждый уходит меньше миллиона сравнений.

Выход

Для каждого образца — строка из трёх чисел: окон, сравнений, вхождений.