Problem C. Cyclic state machine ≡

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

• S — number of the current state of the device;
• C — character in the current position;
• Q — number of the next state of the device;
• H — number of characters to cyclically move the pointer (positive value — to the right, negative value — to the left).

The device will stop if:

• device will return to same position and same state as previously visited; or
• the table will contain no action for the current position and state.

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

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