/* test generator uses testlib.h: https://github.com/MikeMirzayanov/testlib/blob/master/testlib.h
   arguments:
    - first - name of the test that will be generated
    - second - value of n
    - third - value of q
    - fourth - value of f
    - fifth - value of u
    - sixth - type of test
        = 0 - random numbers with values up to seventh parameter
        = 1 - special numbers with seventh parameter as minimum distance between repetitions
        = 2 - special numbers with seventh parameter as minimum distance between repetitions and rarer third occurance
    - seventh - value for the type of test
    - eighth - bigger segments in queries */
#include "testlib.h"
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<unordered_set>
#include<vector>
#include "test_generator.h"
#define MAXN 100000
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

int nodes[4*MAXN];
void build (int ind, int l, int r, vector <int>& init) {
    if (l==r) {
        nodes[ind]=init[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*ind+1,l,mid,init);
    build(2*ind+2,mid+1,r,init);
    nodes[ind]=max(nodes[2*ind+1],nodes[2*ind+2]);
}
int query (int ind, int l, int r, int ql, int qr) {
    if ((ql<=l)&&(r<=qr)) return nodes[ind];
    int mid=(l+r)/2;
    int ans=-1;
    if (ql<=mid) ans=max(ans,query(2*ind+1,l,mid,ql,qr));
    if (qr>mid) ans=max(ans,query(2*ind+2,mid+1,r,ql,qr));
    return ans;
}
void update (int ind, int l, int r, int pos, int val) {
    if (l==r) {
        nodes[ind]=val;
        return ;
    }
    int mid=(l+r)/2;
    if (pos<=mid) update(2*ind+1,l,mid,pos,val);
    else update(2*ind+2,mid+1,r,pos,val);
    nodes[ind]=max(nodes[2*ind+1],nodes[2*ind+2]);
}

int a[MAXN],n;
int prv[MAXN+1],prv2[MAXN+1];
tuple <int, int, int> queries[MAXN];
set <int> inds[MAXN+1];
ordered_set <int> free1;
ordered_set <tuple <int, int, int>> gaps;
int mind;
void change_gaps (int i, int type) {
    int val=a[i];
    auto it=inds[val].find(i);
    it--;
    int prv=(*it);
    it++;
    it++;
    int nxt=(*it);
    it--;
    if (type==-1) {
        gaps.erase({prv, i, val});
        gaps.erase({i, nxt, val});
        if (nxt-prv>=2*mind) gaps.insert({prv, nxt, val});
    }
    else {
        if (i-prv>=2*mind) gaps.insert({prv, i, val});
        if (nxt-i>=2*mind) gaps.insert({i, nxt, val});
        gaps.erase({prv, nxt, val});
    }
}

void change (int i, int type) {
    int val=a[i];
    auto it=inds[val].find(i);
    it--;
    int prv=(*it),prv2=-1;
    if (prv>=0) {
        it--;
        prv2=(*it);
        it++;
    }
    it++;
    it++;
    int nxt=(*it),nxt2=1e9;
    if (nxt<n) {
        it++;
        nxt2=(*it);
        it--;
    }
    it--;
    if (type==-1) {
        update(0,0,n-1,i,-1);
        if (nxt<n) update(0,0,n-1,nxt,prv2);
        if (nxt2<n) update(0,0,n-1,nxt2,prv);
    }
    else {
        update(0,0,n-1,i,prv2);
        if (nxt<n) update(0,0,n-1,nxt,prv);
        if (nxt2<n) update(0,0,n-1,nxt2,i);
    }
}

int main (int argc, char** argv) {
    if (argc==1) {
       cout << "The test generator needs arguments!\n";
       return 0;
    }
    check_tests(argc,argv);
    if (argc<6) {
       cout << "The test generator needs more arguments!\n";
       return 0;
    }
    registerGen(argc,argv,1);
    ofstream fout(argv[1]);
    n=atoll(argv[2]);
    int q=atoll(argv[3]),f=atoll(argv[4]);
    int u=atoll(argv[5]),type=atoll(argv[6]);
    int typev=atoll(argv[7]);
    bool bigger=atoll(argv[8]);
    if (type==0) mind=1;
    else mind=typev;

    for (int v=1; v<=n; v++) {
        inds[v].insert(0-mind);
        inds[v].insert(n-1+mind);
        prv[v]=prv2[v]=-1e9;
    }
    vector <int> nums(n);
    for (int i=0; i<n; i++) {
        if (type==0) a[i]=rnd.next(1,typev);
        else {
            bool rand=rnd.next(2);
            for (int it=1; ; it++) {
                if ((rand==true)||(i<mind)||(it>100)) a[i]=rnd.next(1,n);
                else a[i]=a[rnd.next(0,i-mind)];
                if (i-prv[a[i]]>=mind) {
                    if ((type==1)||(i-prv2[a[i]]>=n/(bigger?3:5))) break;
                }
            }
            prv2[a[i]]=prv[a[i]];
            prv[a[i]]=i;
        }
        inds[a[i]].insert(i);
        nums[i]=a[i];
    }
    vector <int> tmp(n);
    for (int v=1; v<=n; v++) {
        for (auto it=inds[v].begin(); it!=inds[v].end(); it++) {
            if (it==inds[v].begin()) continue;
            it--;
            int prv=(*it),prv2=-1;
            if (it!=inds[v].begin()) {
                it--;
                prv2=(*it);
                it++;
            }
            it++;
            int curr=(*it);
            if (curr-prv>=2*mind) gaps.insert({prv, curr, v});
            if (curr<n) tmp[curr]=prv2;
        }
        if (inds[v].size()==2) free1.insert(v);
    }
    build(0,0,n-1,tmp);

    vector <int> p;
    for (;;) {
        p=rnd.partition(u+1,q-u,0);
        if ((p.front()!=0)&&(p.back()!=0)) break;
    }
    for (int i=0; i<q; i++) {
        get<0>(queries[i])=1;
    }
    int ind=0;
    for (int i=0; i<u; i++) {
        ind+=p[i];
        get<0>(queries[ind])=2;
        ind++;
    }
    for (int i=0; i<q; i++) {
        int t=get<0>(queries[i]);
        if (type==2) {
            if ((i-1)*100/q<i*100/q) cout << i*100/q << "% ";
        }
        if (t==1) {
            int l,r;
            if ((i>0)&&(get<0>(queries[i-1])==2)) {
                int min1=1e9,max1=-1;
                for (int j=i-1; ; j--) {
                    auto [t, ind, v]=queries[j];
                    if (t!=2) break;
                    min1=min(min1,ind);
                    max1=max(max1,ind);
                }
                for (int it=1; ; it++) {
                    l=rnd.next(0,min1);
                    r=rnd.wnext(max1,n-1,bigger?5:0);
                    if ((type<=1)||(query(0,0,n-1,l,r)<l)) break;
                    if (it>100) {
                        for (;;) {
                            int len=rnd.wnext(1,n,bigger?5:0);
                            l=rnd.next(0,n-len);
                            r=l+len-1;
                            if (query(0,0,n-1,l,r)<l) break;
                        }
                        break;
                    }
                }
            }
            else if (rnd.next(3)==0) {
                for (;;) {
                    int len=rnd.wnext(1,n,bigger?5:0);
                    l=rnd.next(0,n-len);
                    r=l+len-1;
                    if ((type<=1)||(query(0,0,n-1,l,r)<l)) break;
                }
            }
            else {
                for (;;) {
                    int len;
                    if (type==0) len=rnd.wnext(1,n,bigger?3:-3);
                    else if (type==1) len=rnd.wnext(1,min(n,mind*10),bigger?5:0);
                    else len=rnd.wnext(1,n/(bigger?3:5),bigger?5:3);
                    l=rnd.next(0,n-len);
                    r=l+len-1;
                    if ((type<=1)||(query(0,0,n-1,l,r)<l)) break;
                }
            }
            queries[i]={t, l, r};
        }
        else {
            auto [l, r, val]=*gaps.find_by_order(rnd.next(gaps.size()));
            int ind=rnd.next(max(l+mind,0),min(r-mind,n-1));
            if ((type==2)&&(bigger==true)&&(rnd.next(1+100/(MAXN/n))>0)) {
                if (free1.size()>0) val=*free1.find_by_order(rnd.next(free1.size()));
                else {
                    cout << i << " ";
                    if (rnd.next(2)) ind=rnd.wnext(0,mind-1,-3);
                    else ind=rnd.wnext(n-mind,n-1,3);
                }
            }
            change(ind,-1);
            change_gaps(ind,-1);
            inds[a[ind]].erase(ind);
            if (inds[a[ind]].size()==2) free1.insert(a[ind]);
            a[ind]=val;
            if (inds[a[ind]].size()==2) free1.erase(a[ind]);
            inds[a[ind]].insert(ind);
            change(ind,+1);
            change_gaps(ind,+1);
            queries[i]={t, ind, val};
        }
    }
    fout << n << " " << q << endl ;
    fout << f << endl ;
    for (int i=0; i<n; i++) {
        if (i!=0) fout << " ";
        fout << nums[i] ;
    }
    fout << endl ;
    for (int i=0; i<q; i++) {
        auto [t, x, y]=queries[i];
        fout << t << " " << x << " " << y << endl ;
    }
    fout.close();

    cout << "test successfully generated!!!" << endl ;
    validate_test(argc,argv);
    return 0;
}
