## 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

• 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

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.041s 0.008s 15