fork download

copy

#define ARYANC403
/*
  Warn - Don't change next line else you will get WA verdict. Online Judge is configured to give WA if next line is not present.
  "An ideal problem has no test data."
  Author - Aryan Choudhary (@aryanc403)
*/
 
#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")
 
#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
typedef vector<ulli> vui;
 
clock_t time_p=clock();
void aryanc403()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
 
#ifdef ARYANC403
    #define dbg(...) { cerr<<"[ "; __aryanc403__(#__VA_ARGS__, __VA_ARGS__);}
    #undef endl
    template <typename Arg1,typename Arg2>
    ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
        return out<<"("<<x.X<<","<<x.Y<<")";
    }
 
    template <typename Arg1>
    ostream& operator << (ostream& out, const vector<Arg1> &a) {
        out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
    }
 
    template <typename Arg1>
    ostream& operator << (ostream& out, const set<Arg1> &a) {
        out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
    }
 
    template <typename Arg1,typename Arg2>
    ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
        out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
    }
 
    template <typename Arg1>
    void __aryanc403__(const string name, Arg1&& arg1){
        cerr << name << " : " << arg1 << " ] " << endl;
    }
 
    template <typename Arg1, typename... Args>
    void __aryanc403__(const string names, Arg1&& arg1, Args&&... args){
        const string name = names.substr(0,names.find(','));
        cerr<<name<<" : "<<arg1<<" | ";
        __aryanc403__(names.substr(1+(int)name.size()), args...);
    }
#else
    #define dbg(args...)
#endif
 
const lli INF = 0xFFFFFFFFFFFFFFFL;
 
lli seed,seedtgen;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
 
const vector<string> rg={"rax","rbx","rcx"};
const vector<string> rgv={"dl","dx","edx","rdx"};
const lli itn = 25;
 
struct soln{
    private :
    vector<string> a;
    map<string,ulli> st;
 
    public:
    soln()      { a.clear(); st.clear();};
    soln(const map<string,ulli> m)      { a.clear(); st=m;};
 
    void clear(){ a.clear(); st.clear();};
    void prt(string s) { a.pb(s);}
 
    map<string,ulli> getStates() { return st;}
 
    void prtsoln() {
        for(auto x:a)
            cout<<x<<endl;
    }
 
    void setStates(const soln &o){
        st=o.st;
    }
 
    void mergeWithStates(const soln &o){
        st=o.st;
        for(auto x:o.a)
            a.pb(x);
    }
 
    void swap(soln &o){
        st.swap(o.st);
        a.swap(o.a);
    }
 
    void add(soln o) {
 
        if(!o.scr())
            return;
 
        for(auto x:st)
            rst(x.X);
 
        for(auto x:o.a)
            a.pb(x);
        st=o.st;
    }
 
    lli scr(){  return (lli)a.size();   }
    lli bt(string s){  return st[s];   }
 
    void max(soln b){
        if(b.a.empty())
            return;
 
        if(a.empty()||(int)b.a.size()<(int)a.size())
        {
            st.swap(b.st);
            a.swap(b.a);
        }
    }
 
    void rst(string s)
    {
        if(!st[s])
            return;
        st[s]=0;
        prt("xor "+s+" "+s);
    }
 
    void inc(string s)
    {
        st[s]++;
        prt("inc "+s);
    }
 
    void shl(string a,string b)
    {
        if(!st[b])
            return;
        st[a]>>=st[b];
        prt("shl "+a+" "+b);
    }
 
    void add(string a,string b)
    {
        if(!st[b])
            return;
        st[a]+=st[b];
        prt("add "+a+" "+b);
    }
 
    void sub(string a,string b)
    {
        if(!st[b])
            return;
        st[a]-=st[b];
        prt("sub "+a+" "+b);
    }
 
    void xr(string a,string b)
    {
        st[a]^=st[b];
        prt("xor "+a+" "+b);
    }
 
    void nt(string a)
    {
        st[a]=~st[a];
        prt("not "+a);
    }
 
    void mov(string a,string b)
    {
        if(st[a]==st[b])
            return;
        st[a]=st[b];
        prt("mov "+a);
    }
};
 
void printans(soln ans)
{
    cout<<(int)ans.scr()<<endl;
    ans.prtsoln();
    aryanc403();
    exit(0);
}
 
namespace testcase{
    mt19937 rng(seedtgen=chrono::steady_clock::now().time_since_epoch().count());
 
    inline lli rnd(lli l,lli r)
    {return uniform_int_distribution<lli>(l,r)(rng);}
 
    ulli rnd(){
        ulli x=rnd(0,1LL<<32),y=rnd(0,1LL<<32);
        return (x<<32)+y;
    }
 
    vector<vui> test1(){
        vector<vui> a;
        const lli n=64;
        for(int i=0;i<n;++i)
            a.pb({rnd(),rnd(),rnd()});
        dbg("TC 1 Generated.");
        return a;
    }
 
    vector<vui> test2(){
        vector<vui> a;
        vui b;
 
        const lli n=64;
        const ulli on=1;
 
        for(int i=0;i<n;++i)
        {
            for(int j=i;j<n;++j)
            b.pb((on<<i)|(on<<j));
        }
 
        const lli m=(lli)b.size();
        for(int i=0;i<n;++i)
        {
            ulli x=rnd();
            a.pb({x,x^b[rnd(0,m-1)],x^b[rnd(0,m-1)]});
        }
        dbg("TC 2 Generated.");
        return a;
    }
 
    vector<vui> test3(){
        vector<vui> a;
        const lli n=64,bat=8;
        ulli d=0;
        for(int i=0;i<n;++i)
        {
            if(i%bat==0)
                d=rnd();
            ulli x=rnd();
            a.pb({x,x+d,x+2*d});
        }
        dbg("TC 3 Generated.");
        return a;
    }
 
    void applyop(ulli &x,ulli &y)
    {
        bool fl=rnd(0,1);
        ulli a=x,b=y;
        ulli m64=-1;
        ulli m32=m64>>32;
 
        if(fl)
        {
            a&=m32;
            b&=m32;
        }
 
        switch(rnd(0,4))
        {
            case 0:  a+=b;  break;
            case 1:  a-=b;  break;
            case 2:  a|=b;  break;
            case 3:  a&=b;  break;
            case 4:  a^=b;  break;
        }
 
        if(fl)
        {
            a&=m32;
            x>>=32;x<<=32;
            x|=a;
        }
        else
            x=a;
    }
 
    vui test4List(){
        vui l;
        while(true){
            l.clear();
            const lli n=64;
            vui reg({rnd(),rnd(),rnd()});
 
            unsigned long long last_l = 0;
            bool ok = true;
            int mistakes = 0;
            while((lli)l.size()<9*n)
            {
                vui old = reg;
 
                int op_id = rnd(0,5);
                switch(op_id)
                {
                    case 0:   applyop(reg[0],reg[1]);      break;
                    case 1:   applyop(reg[0],reg[2]);      break;
                    case 2:   applyop(reg[1],reg[0]);      break;
                    case 3:   applyop(reg[1],reg[2]);      break;
                    case 4:   applyop(reg[2],reg[0]);      break;
                    case 5:   applyop(reg[2],reg[1]);      break;
                }
                bool mistake_made = false;
                if(l.size()%9 == 6){
                    mistake_made |= l.size() >= 3 && l[l.size()-1] == reg[2];
                    mistake_made |= l.size() >= 6 && l[l.size()-4] == reg[2];
                }
                if(l.size()%9 == 3){
                    mistake_made |= l.size() >= 3 && l[l.size()-1] == reg[2];
                }
                if(mistake_made){
                    reg = old;
                    if(++mistakes > (1<<8)){
                        ok = false;
                        break;
                    }
                    continue;
                }
                l.pb(reg[0]);
                l.pb(reg[1]);
                l.pb(reg[2]);
                last_l = reg[2];
            }
            if(ok) return l;
        }
        assert(false);//never reached
    }
 
    vector<vui> test4(){
        vector<vui> a;
        vui b;
        const lli n=64;
        a.clear();
        b=test4List();
        for(lli i=2;i<9*n;i+=9)
            a.pb({b[i],b[i+3],b[i+6]});
        for(int i = 0; i < n; ++i){
            if(a[i][0] == a[i][1]) assert(false);
            if(a[i][0] == a[i][2]) assert(false);
            if(a[i][1] == a[i][2]) assert(false);
        }
        dbg("TC 4 Generated.");
        return a;
    }
 
    vector<vui> test5(){
        vector<vui> a;
        const lli n=64;
        ulli k=rnd();
        for(int i=0;i<n;++i)
        {
            ulli x=rnd(),y=rnd();
            a.pb({x,y,k-x-y});
        }
        dbg("TC 5 Generated.");
        return a;
    }
 
    void printtc(lli id)
    {
        vector<vui> a;
        switch(id)
        {
            case 1: a=testcase::test1(); break;
            case 2: a=testcase::test2(); break;
            case 3: a=testcase::test3(); break;
            case 4: a=testcase::test4(); break;
            case 5: a=testcase::test5(); break;
        }
 
        cout<<(lli)a.size()<<endl;
        for(auto x:a)
            cout<<x[0]<<" "<<x[1]<<" "<<x[2]<<endl;
 
        //cout<<endl;
        //cout<<"Seed used for generation : "<<seedtgen<<endl;
    }
};
 
namespace load{
 
    lli bcnt(ulli x)
    {
        lli cnt=0;
        while(x)
        {
            if(x&1)
                cnt++;
            x/=2;
        }
        return cnt;
    }
 
    ulli neg(ulli x,int bt)
    {
        ulli on=1;
        ulli lim=on<<bt;
        lim--;
        x=~x;
        x&=lim;
        return x;
    }
 
    void orr(soln &b,ulli &x,ulli d,string s,string ds){
        if(x&d)
        {
            b.xr(s,ds);
            x^=d;
        }
    }
 
    void loadS(soln &b,ulli x,string s)
    {
        b.rst(s);
        if(!x)
            return;
 
        const lli BT=64;
        if(load::bcnt(x)>BT/2)
        {
            loadS(b,~x,s);
            b.nt(s);
            return;
        }
 
        lli i=BT-1;
        ulli on=1;
        while((x&(on<<i))==0)
            i--;
        b.inc(s);
        while(i)
        {
            b.add(s,s);
            i--;
            if(x&(on<<i))
                b.inc(s);
        }
    }
 
    void loadPre(soln &b,vector<pair<ulli,string>> a)
    {
 
        if((lli)a.size()==1)
        {
            loadS(b,a[0].X,a[0].Y);
            return;
        }
 
        string dg=rgv[3];
        // dbg(b.getStates(),a);
        for(auto &x:a)
        {
            // dbg(x.X,b.bt(x.Y));
            x.X^=b.bt(x.Y);
        }
        // dbg("xor",a);
 
        // b.rst(dg);
        ulli d=0;
        while(true)
        {
            bool fl=true;
            for(auto x:a)
                if(x.X)
                    fl=false;
 
            if(fl)
                break;
 
            if(d==0)
            {
                b.inc(dg);
                d++;
            }
            else
            {
                b.add(dg,dg);
                d+=d;
            }
 
            for(auto &x:a)
                orr(b,x.X,d,x.Y,dg);
        }
        // dbg(a);
        b.rst(dg);
    }
 
    void load(soln &b,vector<pair<ulli,string>> a)
    {
        const lli n=(lli)a.size();
        const lli lim=(1LL<<n);
 
        soln bst;
        for(lli msk=0;msk<lim;++msk)
        {
            soln c;
            c.setStates(b);
 
            for(lli i=0;i<n;++i)
            {
                if(msk&(1LL<<i))
                    a[i].X=~a[i].X;
            }
 
            loadPre(c,a);
 
            for(lli i=0;i<n;++i)
            {
                if(msk&(1LL<<i))
                {
                    a[i].X=~a[i].X;
                    c.nt(a[i].Y);
                }
            }
 
            if(msk==0||c.scr()<bst.scr())
                bst.swap(c);
        }
 
        b.mergeWithStates(bst);
        // dbg(b.getStates());
    }
};
 
namespace graph{
    vector<bool> vis;
 
    lli CostCalcPre(vui a)
    {
        lli cost=0;
        if((lli)a.size()==1)
        {
            lli x=0;
            while(x)
            {
                cost+=(x&1);
                x/=2;
                cost++;
            }
            return cost;
        }
 
        ulli d=0;
        while(true)
        {
            bool fl=true;
            for(auto x:a)
                if(x)
                    fl=false;
 
            if(fl)
                break;
 
            if(d==0)
                d++;
            else
                d+=d;
 
            cost++;
            for(auto &x:a)
            {
                if(x&d)
                {
                    cost++;
                    x^=d;
                }
            }
        }
        cost++;
        return cost;
    }
 
    lli costCalc(vui a){
        lli bstCost=INF;
        const lli n=(lli)a.size();
        const lli lim=(1LL<<n);
 
        for(lli msk=0;msk<lim;++msk)
        {
 
            for(lli i=0;i<n;++i)
            {
                if(msk&(1LL<<i))
                    a[i]=~a[i];
            }
            lli cost=0;
 
            cost+=CostCalcPre(a);
 
            for(lli i=0;i<n;++i)
            {
                if(msk&(1LL<<i))
                {
                    a[i]=~a[i];
                    cost++;
                }
            }
 
            bstCost=min(bstCost,cost);
        }
        return bstCost;
    }
 
    lli findCost1(map<string,ulli> st,vui &a)
    {
        vi bid={0,1,2};
        pair<lli,vui> bst={INF,a};
        do{
            lli cost=costCalc({a[bid[0]]^st[rg[0]],a[bid[1]]^st[rg[1]],a[bid[2]]^st[rg[2]]});
            if(bst.X>cost)
                bst={cost,{a[bid[0]],a[bid[1]],a[bid[2]]}};
        }while(std::next_permutation(bid.begin(),bid.end()));
        a=bst.Y;
        return bst.X;
    }
 
    lli findCost2(map<string,ulli> st,vui &a)
    {
        lli bstCost=INF;
        for(lli msk=0;msk<4;++msk)
        {
            lli cost=0;
 
            if(msk&1)
                a[1]^=a[0];
            if(msk&2)
                a[2]^=a[0];
 
            cost+=costCalc({a[0]^st[rg[0]],a[1]^st[rg[1]],a[2]^st[rg[2]]});
 
            if(msk&1)
            {
                a[1]^=a[0];
                cost++;
            }
 
            if(msk&2)
            {
                a[2]^=a[0];
                cost++;
            }
            bstCost=min(bstCost,cost);
        }
        return bstCost;
    }
 
    lli findCost5(map<string,ulli> st,vui &a)
    {
        lli bstCost=INF;
        const lli n=(lli)a.size();
        for(lli i=0;i<n;++i)
        for(lli j=0;j<n;++j)
        {
            if(i==j)
                continue;
            for(lli msk=0;msk<4;++msk)
            {
                lli cost=0;
 
                if(msk&1)            a[i]^=a[3-i-j];
                if(msk&2)            a[j]^=a[3-i-j];
 
                cost+=costCalc({a[i]^st[rg[1]],a[j]^st[rg[2]]});
 
                if(msk&1){  a[i]^=a[3-i-j];     cost++;}
                if(msk&2){  a[j]^=a[3-i-j];     cost++;}
 
                bstCost=min(bstCost,cost);
            }
        }
        return bstCost;
    }
 
    lli findCost(const map<string,ulli> &st,vui &a,lli fl)
    {
        if(fl==1)
            return findCost1(st,a);
        if(fl==2)
            return findCost2(st,a);
        if(fl==5)
            return findCost5(st,a);
        assert(false);
    }
 
    void load1(map<string,ulli> &st,vui a,lli fstplace)
    {
        const int n=3;
        for(int i=fstplace;i<n;++i)
            st[rg[i]]=a[i];
    }
 
    void load(map<string,ulli> &st,vui a,lli fl)
    {
        if(fl==1||fl==2)
        {
            load1(st,a,0);
            return;
        }
 
        if(fl==5)
        {
            load1(st,a,1);
            return;
        }
 
        assert(false);
    }
 
    lli getNext(const map<string,ulli> &st,vector<vui> &a,lli fl)
    {
        ii nxt=mp(0,INF);
        const lli n=(lli)a.size();
        for(lli i=0;i<n;++i)
        {
            if(vis[i])
                continue;
 
            lli cost=findCost(st,a[i],fl);
            if(cost<nxt.Y)
                nxt=mp(i,cost);
        }
 
        vis[nxt.X]=true;
        return nxt.X;
    }
 
    // ii getNext2pair(const map<string,ulli> &st,vector<vui> &a,lli fl)
    // {
    //     ii nxt2=mp(0,0);
    //     lli bstCost=INF;
    //     const lli n=(lli)a.size();
    //     for(lli i=0;i<n;++i)
    //     for(lli j=0;j<n;++j)
    //     {
    //         if(vis[i]||vis[j]||i==j)
    //             continue;
 
    //         lli cost=findCost2pair(st,a[i],a[j],fl);
    //         if(cost<bstCost)
    //         {
    //             nxt2=mp(i,j);
    //             bstCost=cost;
    //         }
    //     }
 
    //     vis[nxt2.X]=true;
    //     vis[nxt2.Y]=true;
    //     return nxt2;
    // }
 
    void solve(vector<vui> a,vector<vui> &ans,lli fl)
    {
        const lli n=(lli)a.size();
        lli cnt=0;
        vis.clear();vis.resize(n,false);
        ans.clear();
        map<string,ulli> st;
        while(cnt<n)
        {
            ans.pb(a[getNext(st,a,fl)]);
            load(st,ans.back(),fl);
            cnt++;
        }
    }
 
    // void solve2(vector<vui> a,vector<vui> &ans,lli fl)
    // {
    //     const lli n=(lli)a.size();
    //     lli cnt=0;
    //     vis.clear();vis.resize(n,false);
    //     ans.clear();
    //     map<string,ulli> st;
    //     while(cnt<n)
    //     {
    //         ii nxt2=getNext2pair(st,a,fl);
    //         ans.pb(a[nxt2.X]);
    //         ans.pb(a[nxt2.Y]);
    //         load2pair(st,{a[nxt2.X],a[nxt2.Y]},fl);
    //         cnt+=2;
    //     }
    // }
};
 
namespace matching{
    // Ref - https://g...content-available-to-author-only...b.com/Ashishgup1/Competitive-Coding/blob/master/Min%20Cost%20Max%20Flow%20-%20Dijkstra.cpp
 
    //Works for negative costs, but does not work for negative cycles
    //Complexity: O(min(E^2 *V log V, E logV * flow))
 
    struct edge
    {
        int to, flow, cap, cost, rev;
    };
 
    struct MinCostMaxFlow
    {
        int nodes;
        vector<int> prio, curflow, prevedge, prevnode, q, pot;
        vector<bool> inqueue;
        vector<vector<edge> > graph;
        MinCostMaxFlow() {}
 
        MinCostMaxFlow(int n): nodes(n), prio(n, 0), curflow(n, 0),
        prevedge(n, 0), prevnode(n, 0), q(n, 0), pot(n, 0), inqueue(n, 0), graph(n) {}
 
        void addEdge(int source, int to, int capacity, int cost)
        {
            edge a = {to, 0, capacity, cost, (int)graph[to].size()};
            edge b = {source, 0, 0, -cost, (int)graph[source].size()};
            graph[source].push_back(a);
            graph[to].push_back(b);
        }
 
        void bellman_ford(int source, vector<int> &dist)
        {
            fill(dist.begin(), dist.end(), INT_MAX);
            dist[source] = 0;
            int qt=0;
            q[qt++] = source;
            for(int qh=0;(qh-qt)%nodes!=0;qh++)
            {
                int u = q[qh%nodes];
                inqueue[u] = false;
                for(auto &e : graph[u])
                {
                    if(e.flow >= e.cap)
                        continue;
                    int v = e.to;
                    int newDist = dist[u] + e.cost;
                    if(dist[v] > newDist)
                    {
                        dist[v] = newDist;
                        if(!inqueue[v])
                        {
                            inqueue[v] = true;
                            q[qt++ % nodes] = v;
                        }
                    }
                }
            }
        }
 
        pair<int, int> minCostFlow(int source, int dest, int maxflow)
        {
            bellman_ford(source, pot);
            int flow = 0;
            int flow_cost = 0;
            while(flow < maxflow)
            {
                priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
                q.push({0, source});
                fill(prio.begin(), prio.end(), INT_MAX);
                prio[source] = 0;
                curflow[source] = INT_MAX;
                while(!q.empty())
                {
                    int d = q.top().first;
                    int u = q.top().second;
                    q.pop();
                    if(d != prio[u])
                        continue;
                    for(int i=0;i<graph[u].size();i++)
                    {
                        edge &e=graph[u][i];
                        int v = e.to;
                        if(e.flow >= e.cap)
                            continue;
                        int newPrio = prio[u] + e.cost + pot[u] - pot[v];
                        if(prio[v] > newPrio)
                        {
                            prio[v] = newPrio;
                            q.push({newPrio, v});
                            prevnode[v] = u;
                            prevedge[v] = i;
                            curflow[v] = min(curflow[u], e.cap - e.flow);
                        }
                    }
                }
                if(prio[dest] == INT_MAX)
                    break;
                for(int i=0;i<nodes;i++)
                    pot[i]+=prio[i];
                int df = min(curflow[dest], maxflow - flow);
                flow += df;
                for(int v=dest;v!=source;v=prevnode[v])
                {
                    edge &e = graph[prevnode[v]][prevedge[v]];
                    e.flow += df;
                    graph[v][e.rev].flow -= df;
                    flow_cost += df * e.cost;
                }
            }
            return {flow, flow_cost};
        }
    };
 
    //Problem 1: https://w...content-available-to-author-only...j.com/problems/GREED/
    //Solution 1: http://p...content-available-to-author-only...p.fi/ODRk
 
    //Problem 2 (Double Cost): https://c...content-available-to-author-only...s.com/contest/277/problem/E
    //Solution 2: https://c...content-available-to-author-only...s.com/contest/277/submission/43180845
 
    lli arrange(const vui &a,vui &b)
    {
        const lli n = 3;
        MinCostMaxFlow ans(2*n+2);
        lli i,j;
        repA(i,1,n)
        {
            ans.addEdge(0,i,1,0);
            ans.addEdge(n+i,2*n+1,1,0);
        }
 
        repA(i,1,n)
        repA(j,n+1,2*n)
            ans.addEdge(i,j,1,load::bcnt(a[i-1]^b[j-n-1]));
 
        lli cost=ans.minCostFlow(0,2*n+1,3).Y;
 
        vui c;
        repA(i,1,n)
        {
            for(auto x:ans.graph[i])
                if(x.flow>0)
                {
                    c.pb(b[x.to-n-1]);
                    break;
                }
        }
 
        b.swap(c);
        return cost;
        // sort(b.begin(),b.end());
        // sort(c.begin(),c.end());
        // assert(b==c);
        // dbg(b,c);
    }
};
 
namespace type5{
    ulli k;
 
    bool chk(vector<vui> a)
    {
        for(auto v:a)
        {
            ulli cnt=0;
            for(auto x:v)
                cnt+=x;
            if(cnt!=k)
                return false;
        }
        return true;
    }
 
    void shuffle(vector<vui> &a)
    {
        shuffle(a.begin(),a.end(), rng);
        for(auto &c:a)
            shuffle(c.begin(),c.end(), rng);
        const lli n=(lli)a.size();
        for(lli i=1;i<n;++i)
            matching::arrange(a[i-1],a[i]);
    }
 
    void loadvector(soln &ans,vui a)
    {
        soln bst,c;
        int cnt=0;
        const lli n=(lli)a.size();
 
        for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
        {
            if(i==j)
                continue;
            soln c;
            c.setStates(ans);
            load::load(c,{{a[i],rg[1]},{a[j],rg[2]}});
            if((i==0&&j==1)||c.scr()<bst.scr())
                bst.swap(c);
        }
 
        ans.mergeWithStates(bst);
 
        ans.prt("sub "+rg[0]+" "+rg[1]);
        ans.prt("sub "+rg[0]+" "+rg[2]);
        ans.prt("add "+rg[0]+" "+rg[1]);
        ans.prt("add "+rg[0]+" "+rg[2]);
    }
 
    soln runOnce(vector<vui> a)
    {
        soln ans;
 
        load::load(ans,{{k,rg[0]}});
        for(auto x:a)
            loadvector(ans,x);
 
        return ans;
    }
 
    soln solve(vector<vui> a)
    {
        soln ans;
        k=a[0][0]+a[0][1]+a[0][2];
 
        if(!chk(a))
            return ans;
        graph::solve(a,a,5);
        ans.max(runOnce(a));
 
        // for(int i=0;i<itn;++i)
        // {
            // ans.max(runOnce(a));
        //     shuffle(a);
        // }
 
        dbg("type5 : ",ans.scr());
        return ans;
    }
};
 
namespace type3{
 
    bool chk(vector<vui> a)
    {
        const int n=(int)a.size(),bat=8;
        ulli d=0;
        for(int i=0;i<n;++i)
        {
            if(i%bat==0)
                d=a[i][1]-a[i][0];
            if(a[i][1]-a[i][0]!=d||a[i][2]-a[i][1]!=d)
                return false;
        }
        return true;
    }
 
    void shuffle(vector<vui> &a)
    {
        const int n=(int)a.size(),bat=8;
        vector<vui> b,c;
 
        for(int i=0;i<n;++i)
        {
            c.pb(a[i]);
            if(i==n-1||(i+1)%bat==0)
            {
                shuffle(c.begin(),c.end(), rng);
                for(auto x:c)
                    b.pb(x);
                c.clear();
            }
        }
 
        a.swap(b);
    }
 
    soln runOnce(vector<vui> a)
    {
        soln ans;
        const int n=(int)a.size(),bat=8;
        ulli d=0;
        for(int i=0;i<n;i+=2)
        {
            auto x=a[i],y=a[i+1];
            if(i%bat==0)
            {
                d=x[1]-x[0];
                load::load(ans,{{x[0],rg[1]},{d,rg[0]},{y[0],rg[2]}});
                // d,a1,a2,0;
 
                ans.mov(rgv[3],rg[0]);
                ans.add(rgv[3],rgv[3]); //d,a1,a2,2d
 
                ans.add(rg[0],rg[1]);
                ans.add(rgv[3],rg[1]);//a1+d,a1,a2,a1+2d
                ans.sub(rg[0],rg[1]);
                ans.sub(rgv[3],rg[1]);//d,a1,a2,2d
 
                ans.add(rg[0],rg[2]);
                ans.add(rgv[3],rg[2]);//a2+d,a1,a2,a2+2d
                ans.sub(rg[0],rg[2]);
                ans.sub(rgv[3],rg[2]);//d,a1,a2,2d
 
                ans.rst(rgv[3]);//a1,d,a2,0;
            }
            else
            {
                // *,d,*,0
                load::load(ans,{{x[0],rg[1]},{y[0],rg[2]}});
                // a1,d,a2,0;
 
                ans.mov(rgv[3],rg[0]);
                ans.add(rgv[3],rgv[3]); //d,a1,a2,2d
 
                ans.add(rg[0],rg[1]);
                ans.add(rgv[3],rg[1]);//a1+d,a1,a2,a1+2d
                ans.sub(rg[0],rg[1]);
                ans.sub(rgv[3],rg[1]);//d,a1,a2,2d
 
                ans.add(rg[0],rg[2]);
                ans.add(rgv[3],rg[2]);//a2+d,a1,a2,a2+2d
                ans.sub(rg[0],rg[2]);
                ans.sub(rgv[3],rg[2]);//d,a1,a2,2d
                ans.rst(rgv[3]);//d,a1,a2,0;
            }
        }
 
        return ans;
    }
 
    soln solve(vector<vui> a)
    {
        soln ans;
        if(!chk(a))
            return ans;
 
        for(int i=0;i<itn;++i)
        {
            ans.max(runOnce(a));
            shuffle(a);
        }
 
        dbg("type3 : ",ans.scr());
        return ans;
    }
};
 
namespace type2{
 
    lli bcnt(ulli x)
    {
        lli cnt=0;
        while(x)
        {
            if(x&1)
                cnt++;
            x/=2;
        }
        return cnt;
    }
 
    bool chk(vector<vui> a)
    {
        for(auto x:a)
        {
            if(bcnt(x[0]^x[1])>2||bcnt(x[0]^x[2])>2)
                return false;
        }
        return true;
    }
 
    void loadvector(soln &ans,vui a)
    {
        ans.rst(rg[0]);ans.rst(rg[1]);ans.rst(rg[2]);
        soln bst;
 
        for(lli msk=0;msk<4;++msk)
        {
            soln c;
            // c.setStates(ans);
            if(msk&1)
                a[1]^=a[0];
            if(msk&2)
                a[2]^=a[0];
 
            load::load(c,{{a[0],rg[0]},{a[1],rg[1]},{a[2],rg[2]}});
 
            if(msk&1)
            {
                a[1]^=a[0];
                c.xr(rg[1],rg[0]);
            }
 
            if(msk&2)
            {
                a[2]^=a[0];
                c.xr(rg[2],rg[0]);
            }
 
            if(msk)
                bst.max(c);
            else
                bst.swap(c);
        }
 
        ans.mergeWithStates(bst);
        // dbg(a,ans.getStates());
    }
 
    soln runSorted(vector<vui> a)
    {
        for(auto &x:a)
        {
            if((x[1]^x[0])<(x[2]^x[0]))
                swap(x[1],x[0]);
        }
 
        sort(a.begin(),a.end(),[&](const vui &a,const vui &b){
            ii x={a[1]^a[0],a[2]^a[0]};
            ii y={b[1]^b[0],b[2]^b[0]};
            return x<y;
        });
 
        string s=rg[1];
 
        soln ans;
        ans.inc(s);
 
        for(auto x:a)
        {
            while(ans.bt(s)&&(ans.bt(s)&(x[1]^x[0]))==0)
                ans.add(s,s);
 
            load::load(ans,{{x[0],rg[0]},{x[1]^x[0],rg[1]},{x[2]^x[0],rg[2]}});
            ans.xr(rg[2],rg[0]);
            ans.xr(rg[1],rg[0]);
 
            ans.xr(rg[2],rg[0]);
            ans.xr(rg[1],rg[0]);
        }
 
        dbg("type2sp : ",ans.scr());
        return ans;
    }
 
    soln runOnce(vector<vui> a)
    {
        soln ans;
        for(auto x:a)
            loadvector(ans,x);
        return ans;
    }
 
    soln solve(vector<vui> a)
    {
        soln ans;
        ans.max(runSorted(a));
        graph::solve(a,a,2);
        ans.max(runOnce(a));
        dbg("type2 : ",ans.scr());
        return ans;
    }
};
 
namespace type1{
    void load(soln &ans,vui a)
    {
        // dbg(a);
        load::load(ans,{{a[0],rg[0]},{a[1],rg[1]},{a[2],rg[2]}});
    }
 
    soln runOnce(vector<vui> a)
    {
        soln ans;
        for(auto x:a)
            load(ans,x);
        return ans;
    }
 
    void shuffle(vector<vui> &a)
    {
        shuffle(a.begin(),a.end(), rng);
        for(auto &c:a)
            shuffle(c.begin(),c.end(), rng);
        const lli n=(lli)a.size();
        for(lli i=1;i<n;++i)
            matching::arrange(a[i-1],a[i]);
    }
 
    soln solve(vector<vui> a)
    {
        soln ans;
        graph::solve(a,a,1);
        ans.max(runOnce(a));
        dbg("type1 : ",ans.scr());
        return ans;
    }
};
 
namespace solve{
 
    soln solve(vector<vui> a)
    {
        soln ans;
        ans.max(type1::solve(a));
        ans.max(type5::solve(a));
        ans.max(type2::solve(a));
        ans.max(type3::solve(a));
        return ans;
    }
};
 
namespace complete{
    void run()
    {
        const lli n=64;
        lli scr=0,cnt=0,scrv=0;
 
        //cnt=solve::solve(testcase::test1()).scr();scr+=cnt;
        //dbg(" TC 1 Score : ", cnt, cnt/n);
 
        //cnt=solve::solve(testcase::test2()).scr();scr+=cnt;scrv+=cnt;
        //dbg(" TC 2 Score : ", cnt, cnt/n);
 
        //cnt=solve::solve(testcase::test3()).scr();scr+=cnt;scrv+=cnt;
        //dbg(" TC 3 Score : ", cnt, cnt/n);
 
        for(int i = 0; i < 100; ++i){
            cnt=solve::solve(testcase::test4()).scr();scr+=cnt;
            dbg(" TC 4 Score : ", cnt, cnt/n);
        }
 
        //cnt=solve::solve(testcase::test5()).scr();scr+=cnt;scrv+=cnt;
        //dbg(" TC 5 Score : ", cnt, cnt/n);
 
        //dbg(scr,3*scr/5,scrv);
    }
};
 
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
 
    lli n;
    ulli x,y,z;
    vector<vui> a;
 
#ifdef ARYANC403
 
    if(false)
    {
        complete::run();
        dbg(seed,seedtgen);
        return 0;
    }
 
    {
        for(int i = 0; i < 100; ++i)
            testcase::printtc(4);
        return 0;
    }
 
    a=testcase::test1();
    n=(lli)a.size();
#else
        cin>>n;
        a.clear();a.reserve(n);
        for(int i=0;i<n;++i)
        {
            cin>>x>>y>>z;
            a.pb({x,y,z});
        }
#endif
 
    soln ans;
    ans.max(solve::solve(a));
    // ans.max(type5::solve(a));
 
#ifdef ARYANC403
    dbg(ans.scr()/n,ans.scr());
    dbg(seed,seedtgen);
    // printans(ans);
#else
    printans(ans);
#endif
 
    aryanc403();
    return 0;
}