n = input()
s = raw_input()
# SA-IS (O(nlogn))
def SuffixArray(s):
m = map(ord, s)
m.append(-1)
n = len(m)
def i_large(t, SA, s, bktl):
bkt = {}
for k in bktl: bkt[k] = bktl[k]
for e in SA:
j = e-1
if j>=0 and not t[j]:
SA[bkt[s[j]]] = j
bkt[s[j]] += 1
def i_small(t, SA, s, bkts):
bkt = {}
for k in bkts: bkt[k] = bkts[k]
for e in reversed(SA):
j = e-1
if j>=0 and t[j]:
bkt[s[j]] -= 1
SA[bkt[s[j]]] = j
def SAIS(s, n):
t = [0]*n; LMS = [0]*n
SA = [0]*n
t[-2] = 0; t[-1] = 1
for i in xrange(n-3, -1, -1):
t[i] = 1 if s[i]<s[i+1] or (s[i]==s[i+1] and t[i+1]) else 0
for i in xrange(1, n):
LMS[i] = 1 if t[i] and not t[i-1] else 0
su = 0
bkt = {}
bktl = {}; bkts = {}
for c in s: bkt[c] = bkt.get(c, 0) + 1
for k in sorted(bkt):
bktl[k] = su
su += bkt[k]
bkts[k] = su
for k in bkts: bkt[k] = bkts[k]
for i in xrange(n): SA[i] = -1
for i in xrange(1, n):
if LMS[i]:
bkt[s[i]] -= 1
SA[bkt[s[i]]] = i
i_large(t, SA, s, bktl)
i_small(t, SA, s, bkts)
n1 = 0
for e in SA:
if e>0 and LMS[e]:
SA[n1] = e
n1 += 1
for i in xrange(n1, n): SA[i] = -1
cnt = 0; prev = -1
for i in xrange(n1):
pos = SA[i]
for d in xrange(n):
if prev==-1 or s[pos+d]!=s[prev+d] or t[pos+d]!=t[prev+d]:
cnt += 1
prev = pos
break
elif LMS[pos+d] or LMS[prev+d]: break
pos /= 2
SA[n1+pos] = cnt-1
j = n-1
for i in xrange(n-1, n1-1, -1):
if SA[i]>=0:
SA[j] = SA[i]
j -= 1
if cnt<n1:
SA[:n1] = SAIS(SA[-n1:], n1)
else:
for i in xrange(n1): SA[SA[i-n1]] = i
for k in bkts: bkt[k] = bkts[k]
j = 0
for i in xrange(1, n):
if LMS[i]:
SA[j-n1] = i
j += 1
for i in xrange(n1): SA[i] = SA[SA[i]-n1]
for i in xrange(n1, n): SA[i] = -1
for i in xrange(n1-1, -1, -1):
j = SA[i]; SA[i] = -1
bkt[s[j]] -= 1
SA[bkt[s[j]]] = j
i_large(t, SA, s, bktl)
i_small(t, SA, s, bkts)
return SA
return SAIS(m, n)
rank = [0]*(n+1)
def LCP(s, n, sa):
lcp = [-1]*(n+1)
#rank = [0]*(n+1)
for i in xrange(n+1): rank[sa[i]] = i
h = 0
lcp[0] = 0
for i in xrange(n):
j = sa[rank[i] - 1]
if h > 0: h -= 1
while j+h < n and i+h < n and s[j+h]==s[i+h]:
h += 1
lcp[rank[i] - 1] = h
return lcp
sa = SuffixArray(s)
lcp = LCP(s, n, sa)
# LCP StarrySkyTree
class LCPSST:
def __init__(self, sa, lcp):
n0 = len(lcp)
n = 1
while n < n0:
n *= 2
self.n = n
self.data = data = [10**9]*(2*n)
self.sa = sa
for i in xrange(n0):
data[i+n-1] = lcp[i]
for i in xrange(n-2, -1, -1):
data[i] = min(data[2*i+1], data[2*i+2])
def __query(self, a, b, k, l, r):
if r <= a or b <= l:
return 10**9
if a <= l and r <= b:
return self.data[k]
else:
vl = self.__query(a, b, 2*k+1, l, (l + r) / 2)
vr = self.__query(a, b, 2*k+2, (l + r) / 2, r)
return min(vl, vr)
def __call__(self, i, j):
sa = self.sa
a = rank[i]; b = rank[j]
#print rank[i], rank[j]
if a > b:
a,b = b,a
return self.__query(a, b, 0, 0, self.n)
lcpq = LCPSST(sa, lcp)
# i < j
# XXXXXX YYY
# YYY XXXXXX
def comp(i, j):
res = 1
if i > j:
i,j = j,i
res = -1
r = lcpq(i, j)
#print i, j, r, n-(j-i)
if r < n-j:
return cmp(rank[i], rank[j])*res
r = lcpq(n+i-j+1, i)
#print n+i-j+1, i, r
if r < j-i:
return cmp(rank[n+i-j+1], rank[i])*res
return 0
a = range(0, n)
a.sort(cmp=comp)
print "\n".join(map(str, map(lambda x: x+1, a)))