#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int rk[N],height[N],sa[N],x[N],y[N],c[N],n,m;
char s[N];
void get_sa(){
    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<<=1){
        int num=0;
        for(int i=n-k+1;i<=n;i++)y[++num]=i;
        for(int i=1;i<=n;i++)
        if(sa[i]>k)y[++num]=sa[i]-k;
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[x[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],y[i]=0;
        swap(x,y);
        x[sa[1]]=1,num=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])?num:++num;
        if(num==n)break;
        m=num;
    }
}



void get_height(){
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;i++){
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k])k++;
        height[rk[i]]=k;
    }
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1),m=122;
    get_sa();
    get_height();
    for(int i=1;i<=n;i++)
    printf("%d ",sa[i]);
    puts("");
    for(int i=1;i<=n;i++)
    printf("%d ",height[i]);
}

#include<iostream>
#include<algorithm>
using namespace std;
const double eps=1e-8;
int main(){
    double a;
    scanf("%lf",&a);
    double l=-1e4+10, r=1e4+10;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(mid*mid*mid<=a)l=mid;
        else r=mid;
    }
    printf("%.6lf",r);
}

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct Edge{
    int v,next,w;
}edge[N<<1];
int head[N],tot,n,m;;
struct Node{
    int v,val;
    bool operator<(const Node&a)const{
        return val>a.val;
    }
};
void add(int u,int v,int w){
    edge[++tot]={v,head[u],w};
    head[u]=tot;
}
bool vis[N];
int dis[N];
void prim(){
    priority_queue<Node>q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({1,0});
    int cnt=1,ans=0;
    while(q.size()&&cnt<=n){
        int u=q.top().v;
        q.pop();
        if(vis[u])continue;
        ans+=dis[u];
        cnt++;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].v;
            int w=edge[i].w;
            if(!vis[v]&&dis[v]>w){
                dis[v]=w;
                q.push({v,w});
            }
        }
    }
    if(cnt<n)puts("impossible");
    else printf("%d",ans);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    prim();
}

#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e5+10;
int main(){
    string a;
    cin>>a;
    int n=a.size();
    if(a[0]=='-'){
        cout<<'-';
        n--;
    }
    reverse(a.begin(),a.end());
    int flag=0;
    for(int i=0;i<n;i++){
        if(flag)cout<<a[i];
        else if(a[i]!='0'){
            flag=1;
            cout<<a[i];
        }
    }
    return 0;
}

#include<iostream>
using namespace std;
const int N=2e5+10;
int primes[N],cnt;
bool st[N];
void init(){
    int n=N-1;
    for(int i=2;i<=n;i++){
        if(!st[i])primes[++cnt]=i;
        for(int j=1;primes[j]<=n/i;j++){
            st[i*primes[j]]=1;
            if(i%primes[j]==0)break;
        }
    }
}
int main(){
    init();
    int n;
    cin>>n;
    int maxv=1;
    for(int i=1;i<=cnt;i++){
        if(n%primes[i]==0){
            maxv=max(maxv,primes[i]);
            while(n%primes[i]==0){
                n/=primes[i];
            }
        }
    }
    if(n>1)maxv=max(maxv,n);
    cout<<maxv;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int check(int x){
    int cnt=0;
    while(x){
        if(x%10==2)cnt++;
        x/=10;
    }
    return cnt;
}
int main(){
    int L,R;
    cin>>L>>R;
    int cnt=0;
    for(int i=L;i<=R;i++)
    cnt+=check(i);
    cout<<cnt;
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int main(){
    int A,B,L;
    int a,b;
    cin>>A>>B>>L;
    double d=100000;
    for(int i=1;i<=L;i++)
        for(int j=1;j<=L;j++){
            double x=(double)i/j;
            double X=(double)A/B;
            if(x>=X&&x-X<d){
                d=x-X;
                a=i;
                b=j;
            }
        }

    cout<<a<<" "<<b<<endl;
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e5+10;
int main(){
    int n;
    scanf("%d",&n);
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        mp[x]++;
    }
    cout<<mp.size()<<endl;
    for(auto t:mp){
        cout<<t.first<<" ";
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
int a[N],b[N];
int main(){
    int maxv=0,ans=0;
    for(int i=1;i<=7;i++){
        scanf("%d %d",&a[i],&b[i]);
        if(a[i]+b[i]>maxv&&a[i]+b[i]>8){
            maxv=a[i]+ b[i];
            ans=i;
        }
    }
    cout<<ans;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    int n;
    for(int i=1;i<=10;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&n);
    int res=0;
    for(int i=1;i<=10;i++){
        if(n+30>=a[i])res++;
    }
    cout<<res;
}