24 hour archive: Problem
3647  Shift 3647  Shift 3647  Shift
Statistics  Sub: 258  AC: 53  AC%: 20,54  Score: 2,56 
Created by  José Luis Castrillón Garrido 
Added by  jlcastrillon (20160524) 
Limits 
Total Time: 10000 MS

Test Time:
1000 MS
Memory: 512 MB  Output: 64 MB  Size:
16 KB

Enabled languages  
Available in 
Description
Bono is composing the best song of his life and for this reason he bought a new guitar. A song comes out of the guitar as a string of lowercase characters. Bono loves to play with the songs he writes. This time he is interested in the Shifts of the song.
Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Bono is composing the best song of his life and for this reason he bought a new guitar. A song comes out of the guitar as a string of lowercase characters. Bono loves to play with the songs he writes. This time he is interested in the Shifts of the song.
Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Bono is composing the best song of his life and for this reason he bought a new guitar. A song comes out of the guitar as a string of lowercase characters. Bono loves to play with the songs he writes. This time he is interested in the Shifts of the song.
Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Let T denote some song(a string) of length n, a Shift(T, k) is the left cyclic shift of T by k1 positions. Knowing this, Bono wants you to order all the shifts of his new song. That is, you have to find a permutation P[1..n] such that Shift(T, P[1]), Shift(T, P[2]), ..., Shift(T, P[n]) is a list of cyclic shifts of T sorted in lexicographical order. In case of having two equal shifts, print first the one with smaller index. More formally, if Shift(T, i) is equal to Shift(T, j) and i < j then print i before j.
Input specification
The first and only line of input contains the new song T (1 <= length(T) <= 100000).
;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA
The first and only line of input contains the new song T (1 <= length(T) <= 100000).
;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA
The first and only line of input contains the new song T (1 <= length(T) <= 100000).
;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA
Output specification
Output N lines indicating the positions of the ordered Shifts.
Output N lines indicating the positions of the ordered Shifts.
The first and only line of input contains the new song T (1 <= length(T) <= 100000).
;jsessionid=B6A63B8FA9CB2D8D9E756C4193E939DA
Sample input
aba
Sample output
3
1
2
Hint(s)
The ordered shifts for aba are:
3 aab
1 aba
2 baa
3 aab
1 aba
2 baa
The ordered shifts for aba are:
3 aab
1 aba
2 baa
3 aab
1 aba
2 baa
The ordered shifts for aba are:
3 aab
1 aba
2 baa
3 aab
1 aba
2 baa