For a non-empty string $S$ and $T$, if $T$ is both a prefix and a suffix of $S$, and $|T|<|S|$, then $T$ (or $|T|$) is called a border of $S$.

Given a string $S$ and $q$ queries, each query provides a substring of $S$. For each query, find the length of the shortest border, the length of the longest border, and the total number of borders for that substring.

Input

The first line contains a string $S$. The second line contains an integer $q$. The next $q$ lines each contain two integers $l$ and $r$, representing the query for the substring $S[l \cdots r]$ (0-indexed).

Output

For each query, output a single line. If there are no borders, output -1. Otherwise, output three integers representing the length of the shortest border, the length of the longest border, and the number of borders.

Examples

Input 1

abacaba
2
0 6
1 2

Output 1

1 3 2
-1

Input 2

aaaaaa
1
0 5

Output 2

1 5 5

Subtasks

$1 \le |S|, q \le 2 \times 10^5$