var  s:ansistring;  n,tot:longint;  c,x,y,rank,sa:array[0..1000]of longint;procedure first;var  i:longint;begin  readln(s);  n:=length(s);  for i:=1 to n do x[i]:=ord(s[i]);  fillchar(c,sizeof(c),0);  for i:=1 to n do inc(c[x[i]]);  for i:=1 to 128 do inc(c[i],c[i-1]);  for i:=1 to n do begin    sa[c[x[i]]]:=i;    dec(c[x[i]]);  end;  tot:=1;  rank[sa[1]]:=1;  for i:=2 to n do begin    if x[sa[i]]<>x[sa[i-1]] then inc(tot);    rank[sa[i]]:=tot;  end;end;procedure calcsa;var  i,p:longint;begin  p:=1;  while p<n do begin    for i:=1 to n-p do y[i]:=rank[i+p];    for i:=n-p+1 to n do y[i]:=0;    fillchar(c,sizeof(c),0);    for i:=1 to n do inc(c[y[i]]);    for i:=1 to n do inc(c[i],c[i-1]);    for i:=1 to n do begin      sa[c[y[i]]]:=i;      dec(c[y[i]]);    end;    for i:=1 to n do x[i]:=rank[i];    fillchar(c,sizeof(c),0);    for i:=1 to n do inc(c[x[i]]);    for i:=1 to n do inc(c[i],c[i-1]);    for i:=n downto 1 do begin      y[sa[i]]:=c[x[sa[i]]];      dec(c[x[sa[i]]]);    end;    for i:=1 to n do sa[y[i]]:=i;    tot:=1;    rank[sa[1]]:=1;    for i:=2 to n do begin      if (x[sa[i]]<>x[sa[i-1]]) or (x[sa[i]+p]<>x[sa[i-1]+p]) then inc(tot);      rank[sa[i]]:=tot;    end;    if tot=n then break;    p:=p<<1;  end;  for i:=1 to n do    sa[rank[i]]:=i;  for i:=1 to n do write(sa[i],‘ ‘);  writeln;  for i:=1 to n do write(rank[i],‘ ‘);end;begin  first;  calcsa;  readln;  readln;end.

var  s:ansistring;  n,tot:longint;  c,x,y,rank,sa:array[0..1000]of longint;procedure swap(var j,k:longint);var  i:longint;begin  i:=j;  j:=k;  k:=i;end;procedure qsort(l,r:longint);var  i,j,mid:longint;begin  i:=l;  j:=r;  mid:=x[(l+r) div 2];  repeat    while x[i]<mid do inc(i);    while x[j]>mid do dec(j);    if i<=j then begin      swap(x[i],x[j]);      swap(y[i],y[j]);      inc(i);      dec(j);    end;  until i>j;  if i<r then qsort(i,r);  if l<j then qsort(l,j);end;procedure first;var  i:longint;begin  readln(s);  n:=length(s);  {  //如果n太大用快排据说会快？  for i:=1 to n do begin    x[i]:=ord(s[i]);    y[i]:=i;  end;  qsort(1,n);  for i:=1 to n do sa[i]:=y[i];  tot:=1;  rank[sa[1]]:=1;  for i:=2 to n do begin    if x[i]<>x[i-1] then inc(tot);    rank[sa[i]]:=tot;  end;  }  for i:=1 to n do x[i]:=ord(s[i]);  fillchar(c,sizeof(c),0);  for i:=1 to n do inc(c[x[i]]);  for i:=1 to 128 do inc(c[i],c[i-1]);  for i:=1 to n do begin    sa[c[x[i]]]:=i;    dec(c[x[i]]);  end;  tot:=1;  rank[sa[1]]:=1;  for i:=2 to n do begin    if x[sa[i]]<>x[sa[i-1]] then inc(tot);    rank[sa[i]]:=tot;  end;end;procedure calcsa;var  i,p,sum:longint;begin  p:=1;  while p<n do begin    sum:=0;    for i:=n-p+1 to n do begin      inc(sum);      y[sum]:=i;    end;    for i:=1 to n do      if sa[i]>p then begin        inc(sum);        y[sum]:=sa[i]-p;        if sum=n then break;      end;    for i:=1 to n do x[i]:=rank[y[i]];    fillchar(c,sizeof(c),0);    for i:=1 to n do inc(c[x[i]]);    for i:=1 to n do inc(c[i],c[i-1]);    for i:=n downto 1 do begin      sa[c[x[i]]]:=y[i];      dec(c[x[i]]);    end;    tot:=1;    x[sa[1]]:=1;    for i:=2 to n do begin      if (rank[sa[i]]<>rank[sa[i-1]]) or (rank[sa[i]+p]<>rank[sa[i-1]+p]) then inc(tot);      x[sa[i]]:=tot;    end;    for i:=1 to n do rank[i]:=x[i];    if tot=n then break;    p:=p<<1;  end;  for i:=1 to n do sa[rank[i]]:=i;  for i:=1 to n do write(sa[i],‘ ‘);  writeln;  for i:=1 to n do write(rank[i],‘ ‘);end;begin  first;  calcsa;  readln;  readln;end.