Andy is a successful farmer. He has a field sized 1 x N tiles, where each tile can be planted a plant. Andy has 26 kind of plants, which is represented by the letter 'a' - 'z'.

Each month Andy has to pay tax to the government. The government in his place is very picky. He wants the tax in the form of a block of tiles. He also demands that the block must contain at least Xi number of plant type Yi. A block of tiles is all the tile from range a to b. To minimize the loss, Andy will pay in the smallest block possible. Help Andy to find the length of the smallest block to satisfy the government.

Input

Starts with a number N. The next line is a string of length N containing the letter 'a' to 'z'. The next line is a number K, and for the next K lines are the Xi and Yi, number and type of plants that must be fulfilled.

Output

Minimum length of block to pay the tax. If Andy can't pay the tax, output "Andy rapopo".

Sample Input 1

5
aabac
3
1 a
1 b
1 c

Sample Output 1

3

Sample Input 2

5
aabac
3
1 a
1 b
2 c

Sample Output 2

Andy rapopo

Time limit is very strict, some language might not be able to pass.