Suffix Automaton

Time limit6sMemory limit1024 MB

Summary

Given a string S, find the k-th distinct substring when all substrings are sorted by length, then lexicographically, and print its first occurrence positions.

Level: Hard8 of 10
Topics: String, String matching, Sorting
Solved: No attempts yet

Problem

JB is the National Olympiad Tutor of Suffix Automaton. Today he comes up with the following problem.

Suppose you have a string $S$ . Write down all the distinct substrings of $S$ . Sort them by length in increasing order. For two strings of the same length, the one that is lexicographically smaller comes first. The result is a sorted sequence $A$ of strings.

JB has $Q$ questions. For each question, he gives you an integer $k$ , and you tell him the $k$ -th string in $A$ .

To simplify the problem, you only need to output the left and right positions in $S$ of the first occurrence of that string.

Input

The first line contains one string $S$ ( $1\leq |S|\leq 10^6$ ), containing only lowercase letters.

The second line contains one integer $Q$ ( $1\leq Q\leq 10^6$ ).

Each of the following $Q$ lines contains one integer $k$ ( $1\leq k\leq 10^{12}$ ).

Output

For each question, print two integers $l, r$ , the left and right positions in $S$ of the first occurrence of the answer string. If $k$ is greater than the length of $A$ , print "-1 -1".

Examples2

Example 1

Input

ccpcguilin
5
1
10
4
8
26

Expected output

Example 2
Input
```
banana
3
5
10
16
```
Expected output
```
1 2
2 5
-1 -1
```