There is a war situation. The enemy have devised an intelligent algorithm to encrypt messages. Now the defense division have intercepted several messages and got some clues. But they are stuck in the middle of nowhere. They don't know how to move ahead to further decode the messages sent. They need your help as they believe that you are the only one who is capable enough to break this code.

They have shared the following details with you. Can you help them break the codes:

1. The intercepted code has been processed according to some of the clues and you are then given the remaining code C to decode.
2. This code C only contains lowercase alphabets.
3. It has been found out by the clues that the code C should be decoded by Caesar Cipher with offset m first, before moving any further. The offset m is also known. This should be done by left shifting the characters of code C by offset m. For more understanding about left shifting refer example.
4. After deciphering, code C becomes code C'. Now C' is believed to contain a hidden message H which has some indirect reference to information regarding to some person, place or order. This hidden message H is nothing but a substring of the code C'.
5. The H is believed to have exactly k different characters.
6. The minimum and maximum possible lengths of H are known to be a and b respectively.
7. Moreover it is known that H would not appear before Ath position and would not end after Bth position as these remaining characters (with positions i such that (i < A) and (i > B)) have different meanings which they have already found out.(Assume zero-indexing)

Now it is highly possible that you happen to find more than one possibilities for H then in that case you must select the one possibility in which it starts before other possibilities. Even after doing this, still you might have more than one possibilities. In that case you should select the one that ends before than others.

But it is also possible in some cases that you may not even find a single possibility for H. Then you consider it as a goof.

Remember these messages may be nonsensical to you but the defense division may get very important information from it. Help the defense division for glory. May the force be with you.

Input:

First line contains code C which would be a string with only lowercase characters.
Second line contains two integers m and Q suggesting offset for Caesar cipher and number of queries. (There can be different messages with different properties for same code, so just to make sure about that defense division has came up with these Q queries.)
The next Q lines will contain Q queries.
Each Query will contain 5 space separated integers k, a, b, A, B (Not Kabab :P). These variable names have same meaning as described in question.

Output:

For each query,
1. If you can find such H then you need to output one line with 2 space separated integers l and r denoting the start and end position of H in code.
2. If you can't find such H then output one line with word "GOOF".

Constraints:

1. 1 <= (Length of Code C) <= 10^5+7
2. Code C contains only lowercase letters a-z.
3. 0 <= m <= 25
4. 1 <= Q <= 10^5+7
5. 1 <= k <= 26
6. 1 <= a <= b <= (Length of Code C)
7. 0 <= A <= B <= (Length of Code C) - 1

Example Input:

dppm
1 3
1 1 3 0 3
1 2 3 0 3
1 3 3 0 3

Example Output:

0 0
1 2
GOOF

Author: Suparshva Mehta