Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 200010

char s[MAXN];

int n;

int sa[MAXN],t1[MAXN],t2[MAXN],c[MAXN];

void makeSA(int n,int m)

{

	int p;

	int *x = t1,*y = t2;

	for(int i = 1;i <= m;++i)c[i] = 0;

	for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

	for(int i = 1;i <= m;++i)c[i] += c[i - 1];

	for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(int i = 1;i <= n;++i)y[i] = 0;

		for(int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k; 

		for(int i = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		swap(x,y);

		p = 1;x[sa[1]] = 1;

		for(int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		} 

		if(p >= n)break;

		m = p;

	}

	return;

}

int main()

{

	scanf("%s",s + 1);

	n = 0;

	while(s[n + 1] != '\r' && s[n + 1] != '\n' && s[n + 1] != '\0')++n;

	for(int i = 1;i <= n;++i)s[i + n] = s[i];

	makeSA(2 * n,128);

	for(int i = 1;i <= 2 * n;++i)

	{

		if(sa[i] <= n)

		{

			cout << s[sa[i] + n - 1];

		}

	}

	cout << endl;

	return 0;

}