BIC 5.1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e5 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const string &a, const string &b)
{
    for(ll i=0; i<a.size(); i++)
    {
        if(a[i]!=b[i] && (a[i]=='$' || b[i]=='$'))
        {

            if(a[i]=='$')return 1;

            else if(b[i]=='$')return 0;
        }

        else if(a[i]<b[i])return 1;

        else if(a[i]>b[i])return 0;
    }

    return 1;
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}



void printCycleRotation(vector<string>cyclicRotation)
{

    for(auto x : cyclicRotation)
        cout<<x<<endl;
}

string BwtGenome(vector<string>cyclicRotation)
{
    string ans;
    for(auto x : cyclicRotation)
        ans+=x.back();

        return ans;
}

void RleString(string bwtGenome)
{
      cout<<"RLE(BWT((Genome)) : ";
    ll i=0,n=bwtGenome.size();
    while(i<n)
    {
        ll now=i;

        while(i<n && bwtGenome[now]==bwtGenome[i])
            i++;

        cout<<bwtGenome[now]<<i-now;


    }

    cout<<endl;
}
int main()
{

    fastread();

    ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

    bool flag=false;



    string genome;

    cout<<"input the genome"<<endl;

    cin>>genome;

    string temp=genome;

    n=genome.size();



    if(temp[n-1]!='$')
    {
        temp+='$';

        n++;
    }




    vector<string>cyclicRotation;

    cout<<"\nAll cyclic Rotation of "<<temp<<endl<<endl;

    cyclicRotation.eb(temp);

    while(temp[n-2]!='$')
    {
        temp=temp[n-1]+temp;
        temp.pop_back();

        cyclicRotation.eb(temp);
    }


    printCycleRotation(cyclicRotation);


    cout<<"\nSort The lexiographically \n"<<endl;

    sort(cyclicRotation.begin(),cyclicRotation.end(),compare);

    printCycleRotation(cyclicRotation);

    string BWTGENOME=BwtGenome(cyclicRotation);

    cout<<"BWT(Genome) is  : "<<BWTGENOME<<endl;




    RleString(BWTGENOME);









}


//GCAGGGTGCA