문자열 $S$와 $Q$개의 구간이 주어진다. 구간은 입력으로 주어진 순서대로 $1$번부터 $Q$번까지 번호가 매겨져 있으며, $i$번 구간은 두 정수 $l_i$, $r_i$로 나타낸다.

문자열 $S$의 문자는 왼쪽부터 차례대로 $1$번부터 $|S|$번까지 번호가 매겨져 있다. $1\le l\le r\le |S|$에 대해, $S[l,r]$은 $S$의 $l$번째 문자부터 $r$번째 문자까지를 순서대로 이어 붙인 부분문자열을 의미한다. 각 $i$에 대해 $X_i=S[l_i,r_i]$라고 하자.

문자열 $X$의 무한문자열 $X^\infty$은 $X$를 무한히 이어 붙여서 만든 무한 길이의 문자열이다. 즉,

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

이다.

$X_1^\infty,X_2^\infty,\ldots,X_Q^\infty$를 사전순으로 오름차순 정렬한 결과를 출력하여라.

단, 두 무한문자열이 완전히 같은 경우에는 더 번호가 작은 구간이 앞에 오도록 한다. 즉, $X_i^\infty=X_j^\infty$이고 $i

입력

첫째 줄에 알파벳 소문자로만 이루어진 문자열 $S$가 주어진다. ($2\le |S|\le 150\,000$)

둘째 줄에 구간의 개수 $Q$가 주어진다. ($1\le Q\le 1\,000\,000$)

이후 $Q$개의 줄에 걸쳐 각 구간을 나타내는 두 정수 $l_i$, $r_i$가 공백을 사이에 두고 주어진다. ($1\le l_i\le r_i\le |S|$)

출력

정렬된 순서대로 구간의 번호를 공백으로 구분하여 출력한다.

구간의 번호는 입력으로 주어진 순서대로 $1,2,\ldots,Q$이다.

입출력 예시

예시 1

입력

abacaba
4
1 2
1 3
5 6
2 4

출력

2 1 3 4

예시 2

입력

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

출력

5 10 1 2 9 8 3 6 7 4

노트

첫 번째 예제에서 주어진 부분문자열은 $X_1=\mathtt{ab}$, $X_2=\mathtt{aba}$, $X_3=\mathtt{ab}$, $X_4=\mathtt{bac}$이다.

각 부분문자열의 무한문자열을 앞 $6$자리까지 나타내면 다음과 같다.

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

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

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

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

이를 사전순으로 비교하면 $X_2^\infty

따라서 정렬 결과는 $2,1,3,4$이다.

$X_1^\infty$과 $X_3^\infty$은 완전히 같으므로, 더 번호가 작은 $1$번 구간이 $3$번 구간보다 앞에 온다.