Problem C. Cyclic state machine

Author:A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

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.

Input file format

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 format

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.

Constraints

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

Sample tests

No. Input file (input.txt) Output file (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.067s 0.010s 13