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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

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

0 < |T| ≤ 500, 0 ≤ (Si, Qi) < 1000, 0 ≤ |Hi| ≤ |T|,

0 < M ≤ 36 ⋅ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
acabcbabac
4
1 c 2 -1
1 b 1 1
3 a 1 1
2 b 1 -1
2 3
2
9696969676
4
1 9 2 -3
1 6 2 2
3 7 1 1
2 6 1 -3
3 1

0.080s 0.018s 15