Задача M. Циклический автомат ≡

Условие

Вася изобрел устройство, работающее по принципу конечного автомата. На вход ему подается циклическая цепочка (строка) символов, по которой двигается специальный указатель. За один такт устройства оно считывает символ, находящийся в текущей позиции указателя, и выполняет некоторое действие, определенное специальной таблицей команд.

Каждая i-я команда в такой таблице задается набором следующих значений: S_i C_i Q_i H_i, где S_i — текущее состояние устройства; C_i — символ в текущей позиции; Q_i — состояние, в которое следует перейти; H_i указывает величину, на которую необходимо сдвинуть указатель (положительные значения — вправо, отрицательные — влево).

Известно также, что программа прекратит свою работу в одном из следующих случаев:

• если указатель вернется в позицию, в которой он был ранее, приняв при этом то же состояние, что и на момент первого посещения;
• если в таблице команд не будет найдено инструкции, соответствующей текущему состоянию и символу.

Для некоторой заданной строки и таблицы команд требуется определить начальные условия (номер позиции и состояние)
при которых указанное устройство выполнит максимально возможное число шагов.

Формат входного файла

В начале входного файла "input.txt" хранится строка T, состоящая из цифр и строчных символов латинского алфавита.
Далее указано натуральное число M, за которым следует ровно M команд, записанных в указанном выше формате.

Формат выходного файла

Выходной файл "output.txt" должен содержать номер стартовой позиции и начальное состояние.
При этом полагается, что нумерация позиций в строке начинается с нуля.

Ограничения

Гарантируется, что заданная программа является корректной
и не содержит взаимоисключающих инструкций.

0 < |T| ≤ 500, 0 ≤ (S_i, Q_i) < 1000, 0 ≤ |H_i| ≤ |T|,

0 < M ≤ 36 ⋅ 1000

Примеры тестов

acabcbabac
4
1 c 2 -1
1 b 1 1
3 a 1 1
2 b 1 -1

2 3

9696969676
4
1 9 2 -3
1 6 2 2
3 7 1 1
2 6 1 -3

3 1