/** @Author: lyuc* @Date:   2017-08-14 16:17:23* @Last Modified by:   lyuc* @Last Modified time: 2017-08-14 16:56:41*//* 题意：汉语题目不解释 思路：将字符串延长成两段，然后排序，按照前n个后缀的排名进行输出*/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>#define LL long long#define INF 0x3f3f3f3f#define MAXN 200005using namespace std;/****************************************后缀数组模板****************************************/struct SuffixArray{    char s[MAXN];    int sa[MAXN];//保存着排序后的后缀    int rank[MAXN];//保存着每个后缀的名词    int height[MAXN];//保存着相邻前缀的最长公共子序列的长度    int t1[MAXN],t2[MAXN],c[MAXN],n;    int dmin[MAXN][20];    void build_sa(int m)//m为每个后缀后面加的元素，保证在原字符串中不出现    {        int i,*x=t1,*y=t2;        for(i=0;i<m;i++) c[i]=0;        for(i=0;i<n;i++) c[x[i]=s[i]]++;        for(i=1;i<m;i++) c[i]+=c[i-1];        for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;        for(int k=1;k<=n;k<<=1)        {            int p=0;            for(i=n-k;i<n;i++) y[p++]=i;            for(i=0;i<n;i++)if(sa[i]>=k) y[p++]=sa[i]-k;            for(i=0;i<m;i++) c[i]=0;            for(i=0;i<n;i++) c[x[y[i]]]++;            for(i=1;i<m;i++) c[i]+=c[i-1];            for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]] = y[i];            swap(x,y);            p=1,x[sa[0]]=0;            for(i=1;i<n;i++)                x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]? p-1:p++;            if(p>=n) break;            m=p;        }    }    void build_height()//n不能等于1,否则出BUG    {        int i,j,k=0;        for(i=0;i<n;i++)rank[sa[i]]=i;        for(i=0;i<n;i++)        {            if(k)k--;            j=sa[rank[i]-1];            while(s[i+k]==s[j+k])k++;            height[rank[i]]=k;        }    }    void initMin()    {        for(int i=1;i<=n;i++) dmin[i][0]=height[i];        for(int j=1;(1<<j)<=n;j++)            for(int i=1;i+(1<<j)-1<=n;i++)                dmin[i][j]=min(dmin[i][j-1] , dmin[i+(1<<(j-1))][j-1]);    }    int RMQ(int L,int R)//取得范围最小值    {        int k=0;        while((1<<(k+1))<=R-L+1)k++;        return min(dmin[L][k] , dmin[R-(1<<k)+1][k]);    }    int LCP(int i,int j)//求后缀i和j的LCP最长公共前缀    {        int L=rank[i],R=rank[j];        if(L>R) swap(L,R);        L++;//注意这里        return RMQ(L,R);    }}sa;/****************************************后缀数组模板****************************************/struct Node{    int id;    int val;    bool operator < (const Node & other) const{        return val<other.val;    }}node[MAXN];int res[MAXN];int main(){     // freopen("in.txt", "r", stdin);    // freopen("out.txt", "w", stdout);    scanf("%s",sa.s);    int n=strlen(sa.s);    for(int i=n;i<n*2;i++){//双倍        sa.s[i]=sa.s[i-n];    }    sa.s[n*2]=‘\0‘;    sa.n=n*2;    //然后进行排序      sa.build_sa(300);      sa.build_height();      for(int i=0;i<n;i++){          node[i].id=i;          node[i].val=sa.rank[i];      }      sort(node,node+n);//进行排序      for(int i=0;i<n;i++){          res[i]=node[i].id;      }    for(int i=0;i<n;i++){        printf("%c",sa.s[res[i]+n-1]);    }    printf("\n");    return 0;}