K5 debug debug

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}
string S;

int n;

vector <ll> pf, lvp;

const int p = 29, mod = 1e9 + 7;


int nm(char x){
    return x - 'a' + 1;
}

ll H(int l, int r){
    ll k = r - l + 1;
    ll res = pf[r];
    if (l > 0){
        res -= pf[l-1] * lvp[k] % mod;
    }
    if (res < 0) res += mod;
    return res;
}



int l1, r1, l2, r2;

int cmp(){
    int lf, rt, md;
    //бинописком ищем длину наибольшего общего префикса
    lf = 0;
    rt = min(r2 - l2, r1 - l1);
    //cout<<"lf rt = "<<lf<<' '<<rt<<"\n";
    //cout<<"l r = "<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<"\n";
    while (rt - lf > 1){
        md = (lf + rt) / 2;
        ll a,b;
        a = H(l1, l1 + md);
        b = H(l2, l2 + md);
        //cout<<"md = "<<md<<"\n";
        //cout<<"a b = "<<a<<' '<<b<<"\n";
        if (a == b){
            lf = md;
        }
        else rt= md;
    }
    //cout<<"rt = "<<rt<<"\n";
    rt--;
    if (rt<0)rt=0;
    while (S[l1+rt]==S[l2+rt] && l1 + rt <= r1 && l2 + rt <= r2) rt++;
    //cout<<"rt = "<<rt<<"\n";
    if (l1 + rt > r1 && l2 + rt > r2){
        return 0;
    }
    if (l1 + rt > r1) {
        return -1;
    }
    if (l2 + rt > r2){
        return 1;
    }
    if (S[l1 + rt] > S[l2 + rt]){
        //cout<<"four\n";
        return 1;
    }
    if  (S[l1 + rt] < S[l2 + rt]){
        //cout<<"five\n";
        return -1;
    }
    if  (S[l1 + rt] == S[l2 + rt]){
        //cout<<"six\n";
        return 0;
    }
}

string rndS(){
     string res = "";
     int sz = rand() % 100 + 20;
     string alp = "abcdefghijklmnopqrstuvwxyz";
     for (int i = 0;i < sz;++i){
            int id = rand() % alp.size();
            res += alp[id];
     }
     return res;
 }

 int stp(){
     string a,b;
     a = S.substr(l1, r1 - l1 + 1);
     b = S.substr(l2, r2 - l2 + 1);
     if (a > b){
        return 1;
     }
     if (a < b){
        return -1;
     }
     return 0;
 }

 void cpr(pii x){
     cout<<x.first<<' '<<x.second<<"\n";
 }


int main()
{
    //ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	//cin>>S;
	S = rndS();
	n = S.size();
	lvp.assign(n+5, 1);
	for (int i = 1; i<=n;++i) lvp[i] = lvp[i-1] * p % mod;
	pf.assign(n, nm(S[0]));
	for (int i =1;i<n;++i){
        pf[i] = (pf[i-1] * p % mod + nm(S[i])) % mod;
	}
	//int q; cin>>q;
	int ans;
	cout<<S<<"\n";
	vector <vector<int>> lr;
	vector <pii> checker;
	int go=0;
	while (1){
            go++;
        //cin>>l1>>r1>>l2>>r2;
        l1 = rand() % S.size();
        if (go > 2e6){
            cout<<"NOT FOUND\n";
            break;
        }
        r1 = l1 + rand() % (n - l1);
        if (r1 < l1) r1=l1;
        if (r1 >= n) r1=n-1;
        l2 = rand() % S.size();
        r2 = l2 + rand() % (n - l2);
        if (r2 < l2) r2=l2;
        if (r2>=n) r2=n-1;
        ans = cmp();
        int chk = stp();
        //cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<"\n";
        //cout<<"ans = "<<ans<<"\n";
        //cout<<ans<<"\n";
        if (ans != chk){
            //cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<"\n";
            //cout<<"ans= "<<ans<<"\n";
            //cout<<"chk= "<<chk<<"\n";
            vector <int> v = {l1, r1, l2, r2};
            lr.push_back(v);
            checker.push_back({ans, chk});
        }
        if (checker.size() >= 10) break;
	}
	cout<<"CHECKING DONE\n";
	for (int i=0;i<checker.size();++i){
        cv(lr[i]);
        cpr(checker[i]);
        cout<<"\n";
	}
	/*int go=0;
	S = "hqghumeaylnlfdxfircvscxggbwkfnqduxwfnfozvsrtkjprepggxrpnrvyst";
	while (1){
        cin>>l1>>r1>>l2>>r2;
        go++;
        if (l1==-1 && l2==-1 && r1==-1 && r2==-1) break;
        string a = S.substr(l1, r1 - l1 + 1);
        string b = S.substr(l2, r2 - l2 + 1);
        cout<<a<<' '<<b<<"\n";
	}*/
	//мой ответ - верный ответ
	//1 сравниваешь но не учитываешь размер
}
/*
hqghumeaylnlfdxfircvscxggbwkfnqduxwfnfozvsrtkjprepggxrpnrvyst
CHECKING DONE
58 59 58 60
0 -1

17 59 56 56
0 1

4 8 4 25
0 -1

19 52 19 19
0 1

40 44 40 42
0 1

23 59 23 46
0 1

23 46 51 51
0 1

35 47 35 51
0 -1

10 39 29 29
0 1

15 32 12 12
0 1
*/