You are given a string $S$ and $Q$ intervals. The intervals are numbered from $1$ to $Q$ in the order they are given in the input, and the $i$-th interval is represented by two integers $l_i$ and $r_i$.

The characters of $S$ are numbered from $1$ to $|S|$ from left to right. For $1\le l\le r\le |S|$, let $S[l,r]$ denote the substring formed by concatenating the $l$-th through the $r$-th characters of $S$ in order. For each $i$, let $X_i=S[l_i,r_i]$.

The infinite string $X^\infty$ of a string $X$ is the infinite-length string obtained by concatenating infinitely many copies of $X$. In other words,

$$ X^\infty=X\cdot X\cdot X\cdots. $$

Sort $X_1^\infty,X_2^\infty,\ldots,X_Q^\infty$ in ascending lexicographical order and output the resulting order.

When two infinite strings are identical, the interval with the smaller index must come first. In other words, if $X_i^\infty=X_j^\infty$ and $i

Input

The first line contains a string $S$ consisting only of lowercase English letters. ($2\le |S|\le 150\,000$)

The second line contains the number of intervals $Q$. ($1\le Q\le 1\,000\,000$)

Each of the next $Q$ lines contains two integers $l_i$ and $r_i$, separated by a space, representing the $i$-th interval. ($1\le l_i\le r_i\le |S|$)

Output

Print the indices of the intervals in sorted order, separated by spaces.

The intervals are numbered $1,2,\ldots,Q$ in the order they are given in the input.

Examples

Example 1

Input

abacaba
4
1 2
1 3
5 6
2 4

Output

2 1 3 4

Example 2

Input

ababababca
10
1 4
1 6
2 5
9 10
1 1
2 2
8 9
7 10
3 9
10 10

Output

5 10 1 2 9 8 3 6 7 4

Note

In the first example, the given substrings are $X_1=\mathtt{ab}$, $X_2=\mathtt{aba}$, $X_3=\mathtt{ab}$, and $X_4=\mathtt{bac}$.

The first six characters of their corresponding infinite strings are as follows.

• $X_1^\infty=\mathtt{ababab}\cdots$

• $X_2^\infty=\mathtt{abaaba}\cdots$

• $X_3^\infty=\mathtt{ababab}\cdots$

• $X_4^\infty=\mathtt{bacbac}\cdots$

Comparing them lexicographically gives $X_2^\infty

Therefore, the sorted order is $2,1,3,4$.

Since $X_1^\infty$ and $X_3^\infty$ are identical, interval $1$, which has the smaller index, comes before interval $3$.