The Story of Stringland

The king of Stringland is employing an elite force of undercover agents to protect the kingdom from the attack of Integerland. The king has decided to give each of these agents a code name. These code names will be chosen according to the following rules:

• Each agent's code name must be a non-empty sub-string of the string $S$.
• Each agent's code name must be a palindrome.
• Code names of any two agents can’t be the same.

Since the number of possible code names is limited, the king has ensured that the number of agents is equal to the number of possible code names. These agents will operate secretly in Integerland. They can't directly use their code names because strings are not allowed in Integerland. They will communicate with each other using the lexicographical order of their code names. For example, if there are three agents with code names “a”, “b” and “aba”, then “a” will be called 1 because it’s the lexicographically smallest code name, “aba” will be called 2 because it’s the lexicographically second-smallest code name and “b” will be called 3 because it’s the lexicographically third-smallest code name.

But it's very difficult for them to remember the ordering of code names of all the agents. Since you are the royal programmer of Stringland, the king has given you the responsibility to solve this problem.

Your task is to write a program that will take the string $S$ as input and answer $Q$ queries. In each query, it should take an integer $K$ as input and find out the $K$-th lexicographically smallest code name. Since only integers are allowed in Integerland, your program should print two integers $L$ and $R$ as output for each query, where $L$ and $R$ are starting and ending indices (according to 1-based indexing) of the first occurrence of the $K$-th lexicographically smallest code name in the string $S$. If the $K$-th lexicographically smallest code name does not exist, your program should print -1.

Input

First line of the input contains a non-empty string $S$ containing only lowercase English letters. The length of $S$ will not be more than $10^6$.

The second line of the input contains an integer $Q$ ($1 ≤ Q ≤ 10^5$) where $Q$ is the number of queries.

Each of the next $Q$ lines of the input will contain an integer $K$ ($1 ≤ K ≤ 10^6$) as query.

Output

Print $Q$ lines as output where $i$-th line contains the answer of the $i$-th query.

Samples

Input	Output
bab 4 1 2 3 4	2 2 1 1 1 3 -1

Input	Output
aabbcbbacc 5 1 5 10 3 6	1 1 3 4 -1 2 8 3 7

A sub-string of a string $S$ is a contiguous sequence of characters within the string $S$. For example, “a”, “b”, “ab”, “ba”, “bab” are sub-strings of the string “bab”, but “aa”, “bb”, “c” are not.

A palindrome is a sequence of characters which reads the same backward as forward. For example, “a”, “b”, “aa”, “aba” are palindromes, but “ab”, “ba”, “abb”, “baa” are not.