Дана строка $t$ длины $|t|$, а также массив строк $s_i$ длины $n$.

Стоимостью строки $x$ называется количество вхождений в нее специальной строки $t$ как подстроки.

Выберите два индекса $i$ и $j$ $(1 \leq i,j \leq n)$, не обязательно различных, таких, что конкатенация строк $s_i$ и $s_j$ имеет максимальную стоимость среди всех пар $i,j$. Обратите внимание, что строку можно конкатенировать с собой же.

Входные данные

На первой строке находится строка $t$ ($1 \leq |t| \leq 5 \cdot 10^5$), состоящая из строчных букв латинского алфавита.

На второй строке находится одно целое число $n$ ($1 \leq n \leq 5 \cdot 10^5$) – количество строк в массиве.

Следующие $n$ строк содержат каждая по одной строке $s_i$ ($1 \leq |s_i| \leq 5\cdot 10^5$), состоящей из строчных букв латинского алфавита.

Гарантируется, что суммарная длина всех строк $s_i$ не превосходит $5 \cdot 10^5$.

Выходные данные

В первой строке выведите одно число – максимально возможную стоимость конкатенации $s_i$ и $s_j$.

Во второй строке выведите два числа – $i$ и $j$ $(1 \leq i,j \leq n)$, такие что конкатенация $s_i$ и $s_j$ имеет максимально возможную стоимость. Если оптимальных пар несколько, разрешается вывести любую из них.

Подзадачи