|Author:||A. Baranov||Time limit:||1 sec|
|Input file:||input.txt||Memory limit:||256 Mb|
Vasya invented a device working similarly to finite automaton. Device accepts as input a cyclic string of characters, and has a pointer to one of characters. On each step the device reads the character at the current pointer position and executes an action according to a given table.
Action in the table is represented by four values S C Q H, where
The device will stop if:
Your program must, given input sting and a table, determine starting position and state which will cause device to execute maximum possible number of steps until stopping.
First line of input file contains input string T, consisting of small Latin letters and digits. Second line contains integer M — number of commands. Following M lines contain commands in the format described above.
Output file must contain two integers — numbers of staring position and starting state. Positions are numbered from zero. If there are several optimal solutions, output any of them.
Action table contains no more than one action for each pair (position, state).
0 ≤ S, Q < 1000,
0 ≤ |H| ≤ |T|,
0 < |T| ≤ 500, 0 < M ≤ 36 ⋅ 1000
|No.||Input file (
||Output file (|