Alia wants to play with you. She will give you a string (MSG) where ((N = length of MSG) ≤ 10000) and multiple queries(M). Each query consists of an integer value K.

For each query you have to find the Kth substring if all the substrings of the given string are arranged in lexicographically increasing order without any duplicates (no substring will appear twice in the given arrangement). You have to output the starting index of the Kth substring and its size. If the found substring has duplicates then (substring occurs multiple times in the given string), output the smallest index where it occurs.

If the number of substring in the arrangement is less than the value of K, output -1.

Constraints

1 ≤ size of string(MSG) ≤ 10000

1 ≤ number of queries (M) ≤ 100000

1 ≤ K ≤ total number of substrings (not necessarily unique) of MSG;

Note: you have to output indexes as 1-based.

Input

The first line of input will consist of your string and number of queries (M), separated by a space. Next M lines will consist of integer K (as mentioned in the problem).

Output

Your output should consist of M lines as per the answer for each query.

Example

Input:
aaaaa 3
1
2
3

Output:
1 1
1 2
1 3

Explanation:

Our arrangement here will consist of substrings in the following order (a), (aa), (aaa), (aaaa), (aaaaa)

So 1st substring will be "a" and it's occurring at multiple index - (1, 2, 3, 4, 5) out of which the smallest index is 1 and it's size is 1. Hence the answer will be (1, 1).

The same will be for the other two queries.