fork download

copy

#pragma GCC optimize("Ofast")
#include <cstring>
#include <numeric>
#include <set>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <memory>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
//#define assert(x) ;
#define pb push_back
#define REP_ANY(type,i,l,r) for(type i = l; i <= r; ++i)
#define REP_INT(i,l,r) for(int i = l; i <= r; ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define watch(x) cerr << (#x) << " = " << x << '\n'
#define X first
#define Y second
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
bool saving = true;
 
 
const ll MOD = 1e9 + 7;
 
ll ipow(ll x, ll p, ll mod = MOD){
    if(abs(x) >= mod)
        x %= mod;
    if(x < 0)
        x += mod;
    if(p == 0)
        return 1;
    if(p == 1)
        return x;
    return ipow(x * x % mod, p / 2, mod) * ipow(x, p % 2, mod) % mod;
}
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
template <typename F, typename S> static
ostream& operator<<(ostream& stream, const pair<F, S>& t){
    return stream << t.first << ' ' << t.second;
}
template <typename F, typename S> static
istream& operator>>(istream& stream, pair<F, S>& t){
    return stream >> t.first >> t.second;
}
T1 vector<T> unique(vector<T>& arr){
    sort(all(arr));
    arr.erase(unique(all(arr)), arr.end());
    return arr;
}
static string unique(string& s){
    sort(all(s));
    s.erase(unique(all(s)), s.end());
    return s;
}
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
struct DSU{
    vi par;
    int n;
    DSU(int _n):n(_n){
        par.resize(n + 1);
        iota(all(par), 0);
    }
    int getpar(int u){
        if(par[par[u]] == par[u])
            return par[u];
        return par[u] = getpar(par[u]);
    }
    bool unite(int u, int v){
        u = getpar(u);
        v = getpar(v);
        if(u == v)
            return false;
        par[u] = v;
        return true;
    }
};
T1 T sum(vector<T>& arr){
    T ans = 0;
    for(auto x : arr)
        ans += x;
    return ans;
}
T1 T sum(vector<T>&& arr){
    T ans = 0;
    for(auto x : arr)
        ans += x;
    return ans;
}
template <typename COST_TYPE = ll>
struct MaxFlow{
    const COST_TYPE COST_INF = numeric_limits<COST_TYPE>::max();
    const ll FLOW_INF = 1e18;
    bool needs_prep;
    struct FlowTracker{
        ll *cap, *rcap;
        shared_ptr<ll> flow;
        bool dir;
        FlowTracker(){
            dir = 0;
            cap = rcap = NULL;
        }
        FlowTracker(ll *_cap, ll *_rcap, shared_ptr<ll> _flow, int _dir)
            :cap(_cap), rcap(_rcap), flow(_flow), dir(_dir){
            }
        ll rem()const{
            if(dir == 0){
                return *cap - *flow;
            }else{
                return *rcap + *flow;
            }
        }
        void add_flow(ll f){
            if(dir == 0)
                *flow += f;
            else
                *flow -= f;
            assert(*flow <= *cap);
            assert(-*flow <= *rcap);
        }
        operator ll()const{
            return rem();
        }
        void clear(){
            *flow = 0;
        }
        void operator-=(ll x){
            add_flow(x);
        }
        void operator+=(ll x){
            add_flow(-x);
        }
    };
    struct Edge{
        int u, v;
        ll c, rc;
        COST_TYPE cost;
        FlowTracker flow;
        Edge(){}
        Edge(int _u, int _v, ll _c, COST_TYPE _cost = 0)
            :u(_u), v(_v), c(_c), cost(_cost){
                rc = 0;
            }
        void change_cap(ll _c, ll _rc = 0){
            c = _c;
            rc = _rc;
        }
    };
    int source, sink, rt_source, rt_sink;
    MaxFlow(int _source = numeric_limits<int>::min(), int _sink = numeric_limits<int>::min() + 1):source(_source), sink(_sink){
        needs_prep = true;
    }
    vector<vector<int>> adj;
    vector<vector<COST_TYPE>> cost;
    vector<vector<FlowTracker>> cap;
    vector<Edge> edges;
    int add_edge(int u, int v, ll c, COST_TYPE cost = 0){
        needs_prep = true;
        edges.push_back(Edge(u, v, c, cost));
        return sz(edges) - 1;
    }
    vector<int> now, lvl;
    vector<COST_TYPE> pot;
    vi indices;
    void prep(){
        if(!needs_prep){
            for(auto &_ : edges)
                _.flow.clear();
            return;
        }
        needs_prep = false;
        indices = vi{source,sink};
        for(auto& edge : edges){
            indices.push_back(edge.u);
            indices.push_back(edge.v);
        }
        sort(indices.begin(), indices.end());
        indices.erase(unique(indices.begin(), indices.end()), indices.end());
        rt_source = lower_bound(indices.begin(), indices.end(), source) - indices.begin();
        rt_sink = lower_bound(indices.begin(), indices.end(), sink) - indices.begin();
        adj.clear();
        cost.clear();
        cap.clear();
        now.clear();
        lvl.clear();
        pot.clear();
        int max_id = sz(indices) - 1;
        adj.resize(max_id + 1);
        cost.resize(max_id + 1);
        cap.resize(max_id + 1);
        now.resize(max_id + 1);
        lvl.resize(max_id + 1);
        pot.resize(max_id + 1);
 
        vi ordering(sz(edges));
        iota(all(ordering),0);
        random_shuffle(all(ordering));
 
        for(int id : ordering){
            auto &edge = edges[id];
            int u = lower_bound(indices.begin(), indices.end(), edge.u) - indices.begin();
            int v = lower_bound(indices.begin(), indices.end(), edge.v) - indices.begin();
            auto flow = make_shared<ll>(0);
            adj[u].push_back(v);
            cost[u].push_back(edge.cost);
            cap[u].push_back(FlowTracker(&edge.c, &edge.rc, flow, 0));
            if(u != v){
                adj[v].push_back(u);
                cost[v].push_back(-edge.cost);
                cap[v].push_back(FlowTracker(&edge.c, &edge.rc, flow, 1));
            }
            assert(cap[u].back() == edge.c);
            edge.flow = cap[v].back();
        }
    }
    int get_name(int x){
        auto it = lower_bound(all(indices),x);
        if(it == indices.end() || *it != x){
            indices.pb(x);
            unique(indices);
            needs_prep = true;
            it = lower_bound(all(indices),x);
        }
        assert(*it == x);
        return it-indices.begin();
    }
    void set_source(int _source){
        if(source == _source) return;
        source = _source;
        rt_source = get_name(source);
    }
    void set_sink(int _sink){
        if(sink == _sink) return;
        sink = _sink;
        rt_sink = get_name(sink);
    }
    void bellman_ford(){
        vector<COST_TYPE> dist(sz(adj), COST_INF);
        dist[rt_source] = 0;
        //for(int times = 0; times < sz(dist); ++times){
        while(true){
            bool changes = false;
            for(int u = 0; u < sz(adj); ++u)
                for(int i = 0; i < sz(adj[u]); ++i){
                    int v = adj[u][i];
                    if(dist[u] != COST_INF && cap[u][i]){
                        if(dist[v] > dist[u] + cost[u][i]){
                            changes = true;
                            dist[v] = dist[u] + cost[u][i];
                        }
                    }
                }
            if(!changes)
                break;
        }
        pot = dist;
    }
    ll dijkstra(vector<COST_TYPE>& dist, vector<int>& last_node, vector<int>& last_index){
        dist[rt_source] = 0;
        vector<ll> flow(sz(dist));
        flow[rt_source] = FLOW_INF;
        vector<bool> visited(sz(dist));
        priority_queue<pair<COST_TYPE, int>> pq;
        pq.push({0, rt_source});
        while(!pq.empty()){
            int u = pq.top().second;
            pq.pop();
            if(visited[u])
                continue;
            visited[u] = true;
            assert(dist[u] != COST_INF);
            for(int i = 0; i < sz(adj[u]); ++i){
                int v = adj[u][i];
                if(!visited[v] && cap[u][i])
                    if(dist[u] + cost[u][i] + pot[u] - pot[v] < dist[v]){
                        dist[v] = dist[u] + cost[u][i] + pot[u] - pot[v];
                        last_node[v] = u;
                        last_index[v] = i;
                        flow[v] = min(flow[u], (ll)cap[u][i]);
                        pq.push({-dist[v], v});
                    }
            }
        }
        return flow[rt_sink];
    }
    pair<ll, COST_TYPE> min_cost_flow(int _source, int _sink){
        set_source(_source);
        set_sink(_sink);
        prep();
        bool has_negative = false;
        for(auto& edge : edges)
            if(edge.cost < 0)
                has_negative = true;
        if(has_negative)
            bellman_ford();
        ll total_flow = 0;
        COST_TYPE total_cost = 0;
        while(true){
            vector<COST_TYPE> dist(sz(adj), COST_INF);
            vector<int> last_node(sz(dist)), last_index(sz(dist));
            ll flow = dijkstra(dist, last_node, last_index);
            if(flow == 0)
                break;
            for(int u = rt_sink; u != rt_source; u = last_node[u])
                cap[last_node[u]][last_index[u]] -= flow;
            for(int i = 0; i < sz(adj); ++i)
                pot[i] = pot[i] + dist[i];
            total_flow += flow;
            total_cost += pot[rt_sink] * flow;
        }
        return {total_flow, total_cost};
    }
    pair<ll, COST_TYPE> min_cost_flow(){
        return min_cost_flow(source, sink);
    }
};
T1 T max(const vector<T> arr){
    assert(!arr.empty());
    T ans = arr[0];
    for(auto& cur : arr)
        ans = max(ans, cur);
    return ans;
}
T1 T min(const vector<T>& arr){
    assert(!arr.empty());
    T ans = arr[0];
    for(auto& cur : arr)
        ans = min(ans, cur);
    return ans;
}
T1 T max(const set<T>& s){
    assert(!s.empty());
    return *--s.end();
}
T1 T min(const set<T>& s){
    assert(!s.empty());
    return *s.begin();
}
T1 void print(T x, string end = "\n"){
    cout << x << end;
}
T1 void print(vector<vector<T>> arr){
    for(int i = 0; i < sz(arr); ++i){
        cout << "[" << arr[i] << "]";
        if(i + 1 < sz(arr))
            cout << ", ";
    }
    cout << '\n';
}
T1 ostream& print(T b, T e, string sep = " ", ostream& stream = cout){
    for(T it = b; it != e; ++it){
        stream << *it;
        if(it + 1 != e)
            stream << sep;
    }
    return stream;
}
T1 ostream& operator<<(ostream& stream, const vector<T>& t){
    for(int i = 0; i < sz(t); ++i){
        stream << t[i];
        if(i+1 < sz(t))
            stream << ' ';
    }
    return stream;
}
T1 void print(vector<T> arr, string sep = " "){
    if(arr.empty()){
        return;
    }
    print(arr.begin(), arr.end(), sep);
    cout << '\n';
}
typedef vector<ull> vull;
typedef vector<vull> vvull;
int n,type;
vvull a;
int dist[64][64];
vs description;
string last_oper;
ull rx[4];
#define REG string(1,'a'+pos)
#define OPER if(saving){last_oper = string(__func__).substr(1)+last_oper;}
ull *l64(int pos){
    string tmp = " r"+REG+"x";
    if(saving)
        last_oper = tmp+last_oper;
    return &rx[pos];
}
uint *l32(int pos){
    string tmp = " e"+REG+"x";
    if(saving)
        last_oper = tmp+last_oper;
    uint *a = reinterpret_cast<uint*>(&rx[pos]);
    return &a[0];
}
ushort *l16(int pos){
    string tmp = " "+REG+"x";
    if(saving)
        last_oper = tmp+last_oper;
    ushort *a = reinterpret_cast<ushort*>(&rx[pos]);
    return &a[0];
}
uchar *l8(int pos){
    string tmp = " "+REG+"l";
    if(saving)
        last_oper = tmp+last_oper;
    uchar *a = reinterpret_cast<uchar*>(&rx[pos]);
    return &a[0];
}
uchar *u8(int pos){
    string tmp = " "+REG+"h";
    if(saving)
        last_oper = tmp+last_oper;
    uchar *a = reinterpret_cast<uchar*>(&rx[pos]);
    return &a[1];
}
T1 void _inc(T *a){
    *a += 1;
    OPER;
}
T1 void _dec(T *a){
    *a -= 1;
    OPER;
}
T1 void _not(T *a){
    *a = ~*a;
    if(saving)
        last_oper = "not"+last_oper;
}
T1 void _and(T *a, T *b){
    *a = (*a) & (*b);
    OPER;
}
T1 void _or(T *a, T *b){
    *a = (*a) | (*b);
    OPER;
}
T1 void _xor(T *a, T *b){
    *a = (*a) ^ (*b);
    OPER;
}
T1 void _shl(T *a, T *b){
    *a = (*a) << (*b);
    OPER;
}
T1 void _shr(T *a, T *b){
    *a = (*a) >> (*b);
    OPER;
}
T1 void _add(T *a, T *b){
    *a = (*a) + (*b);
    OPER;
}
T1 void _sub(T *a, T *b){
    *a = (*a) - (*b);
    OPER;
}
T1 void _mul(T *a, T *b){
    *a = (*a) * (*b);
    OPER;
}
T1 void _div(T *a, T *b){
    //assert(b);
    *a = (*a) / (*b);
    OPER;
}
T1 void _mod(T *a, T *b){
    //assert(b);
    *a = (*a) % (*b);
    OPER;
}
T1 void _mov(T *a, T *b){
    *a = *b;
    OPER;
}
vvull all_visited;
int cnt_op;
template<typename T = ull*>
void f(void (*oper)(T,T), int i, int j, T (*type)(int) = l64){
    ++cnt_op;
    oper(type(i),type(j));
    if(saving){
        description.pb(last_oper);
        all_visited.pb(vull(rx,rx+4));
        last_oper = "";
    }
}
void f(void (*oper)(uchar*,uchar*), int i, int j, uchar* (*typei)(int), uchar* (*typej)(int)){
    ++cnt_op;
    oper(typei(i),typej(j));
    if(saving){
        description.pb(last_oper);
        all_visited.pb(vull(rx,rx+4));
        last_oper = "";
    }
}
template<typename T = ull*>
void f(void (*oper)(T), int i, T (*type)(int) = l64){
    ++cnt_op;
    oper(type(i));
    if(saving){
        description.pb(last_oper);
        all_visited.pb(vull(rx,rx+4));
        last_oper = "";
    }
}
 
template<typename T = ull*>
ull g(void (*oper)(T,T), int i, int j, T (*type)(int) = l64){
    ull old = rx[i];
    oper(type(i),type(j));
    last_oper = "";
    ull nxt = rx[i];
    rx[i] = old;
    return nxt;
}
ull g(void (*oper)(uchar*,uchar*), int i, int j, uchar* (*typei)(int), uchar* (*typej)(int)){
    ull old = rx[i];
    oper(typei(i),typej(j));
    last_oper = "";
    ull nxt = rx[i];
    rx[i] = old;
    return nxt;
}
template<typename T = ull*>
ull g(void (*oper)(T), int i, T (*type)(int) = l64){
    ull old = rx[i];
    oper(type(i));
    last_oper = "";
    ull nxt = rx[i];
    rx[i] = old;
    return nxt;
}
bool match(vull a, vull b){
    if(a.empty())
        return true;
    sort(all(a));
    sort(all(b));
    if(a.back() == b.back()){
        a.pop_back();
        b.pop_back();
        return match(a,b);
    }
    else{
        b.pop_back();
        return a == b;
    }
}
void check(vvull a){
    set<vull> seen;
    for(auto _ : a){
        sort(all(_));
        seen.insert(_);
    }
    for(auto _ : all_visited){
        sort(all(_));
        rep(i,0,3){
            vull tmp;
            rep(j,0,3)
                if(i != j)
                    tmp.pb(_[j]);
            seen.erase(tmp);
        }
    }
    assert(seen.empty());
}
int bits(ll x){
    return __builtin_popcountll(x);
}
int get_type(){
    int evidence_3 = 0;
    set<ull> sums;
    set<ull> vals;
    for(auto _ : a){
        if(_[2]-_[1] == _[1]-_[0]){
            ++evidence_3;
        }
        sums.insert(sum(_));
        vals.insert(_[0]);
        vals.insert(_[1]);
        vals.insert(_[2]);
    }
    if(evidence_3 >= n) return 3;
    if(sz(sums) == 1) return 5;
    if(sz(vals) <= 3*n-10) return 4;
    bool can_2 = true;
    for(auto _ : a){
        if(bits(_[0]^_[1]) > 4)
            can_2 = false;
        if(bits(_[0]^_[2]) > 4)
            can_2 = false;
    }
    if(can_2)
        return 2;
    return 1;
}
string B(ull x){
    string ans;
    rep(i,0,63){
        if(i && i%8 == 0)
            ans.pb(' ');
        ans.pb(x%2+'0');
        x >>= 1;
    }
    return ans;
}
vull sx;
void save_state(){
    assert(sx.empty());
    sx = vull(rx,rx+4);
}
void load_state(){
    assert(!sx.empty());
    rep(i,0,3)
        rx[i] = sx[i];
    sx.clear();
}
vull get_state(){
    return vull(rx,rx+4);
}
void set_state(vull _state){
    rep(i,0,sz(_state)-1)
        rx[i] = _state[i];
}
ull choose(ull x, ull g){
    ull m = (ull(1)<<48)+(ull(1)<<32)+(ull(1)<<16);
    rep(t,0,1){
        rep(i,0,7)
            if((((x*m)^g)>>(48+i))%2)
                x ^= ull(1)<<i;
        rep(i,8,15)
            if((((x*m)^g)>>(16+i))%2)
                x ^= ull(1)<<i;
        rep(i,24,31)
            if((((x*m)^g)>>(16+i))%2)
                x ^= ull(1)<<i;
 
        rep(i,40,47)
            if((((x*m)^g)>>(16+i))%2)
                x ^= ull(1)<<i;
    }
 
    ull mask = (-1ull)^((ull(1)<<40)-1)^((ull(1)<<32)-1)^((ull(1)<<24)-1);
    if((((x*m)^g)&mask))
        throw 1;
    return x;
}
ull fbin(string s){
    ull ans = 0;
    reverse(all(s));
    for(char c : s){
        ans <<= 1;
        ans += c-'0';
    }
    return ans;
}
void make_rx3_rem(){
    ull rem = 0;
    rem ^= 1ull<<32;
    rem ^= 1ull<<16;
    if((rx[3]&rx[0])==rem)
        f(_and,3,0);
    else if((rx[3]&rx[1])==rem)
        f(_and,3,1);
    else if((rx[3]&rx[2])==rem)
        f(_and,3,2);
    else if((rx[3]&~rx[0])==rem){
        f(_not,0);
        f(_and,3,0);
        f(_not,0);
    }
    else if((rx[3]&~rx[1])==rem){
        f(_not,1);
        f(_and,3,1);
        f(_not,1);
    }
    else if((rx[3]&~rx[2])==rem){
        f(_not,2);
        f(_and,3,2);
        f(_not,2);
    }
    else if((rx[3]&(rx[0]^rx[1]))==rem){
        f(_xor,0,1);
        f(_and,3,0);
        f(_xor,0,1);
    }
    else if((rx[3]&(rx[2]^rx[1]))==rem){
        f(_xor,2,1);
        f(_and,3,2);
        f(_xor,2,1);
    }
    else if((rx[3]&(rx[2]^rx[0]))==rem){
        f(_xor,2,0);
        f(_and,3,2);
        f(_xor,2,0);
    }
    else if((rx[3]&(~rx[0]^rx[1]))==rem){
        f(_not,0);
        f(_xor,0,1);
        f(_and,3,0);
        f(_xor,0,1);
        f(_not,0);
    }
    else if((rx[3]&(~rx[2]^rx[1]))==rem){
        f(_not,2);
        f(_xor,2,1);
        f(_and,3,2);
        f(_xor,2,1);
        f(_not,2);
    }
    else if((rx[3]&(~rx[2]^rx[0]))==rem){
        f(_not,2);
        f(_xor,2,0);
        f(_and,3,2);
        f(_xor,2,0);
        f(_not,2);
    }
    else if((rx[3]&(rx[0]^rx[1]^rx[2]))==rem){
        f(_xor,0,1);
        f(_xor,0,2);
        f(_and,3,0);
        f(_xor,0,1);
        f(_xor,0,2);
    }
    else{
        f(_sub,3,3); //0
        f(_inc,3,u8); //8
        f(_mul,3,3); //16
        f(_mul,3,3); //32
        f(_inc,3,u8); //32,8
        f(_mul,3,3,l32); //32,16
        assert(rx[3]==rem);
    }
}
void inner16(vull goal){
    vull intermediate(3);
    ull m = (ull(1)<<48)+(ull(1)<<32)+(ull(1)<<16);
    rep(i,0,2){
        try{
            intermediate[i] = choose(rx[i],goal[i]);
        }catch(...){
            f(_sub,i,i);
            intermediate[i] = choose(rx[i],goal[i]);
        }
    }
    rep(i,0,7){
        rep(j,0,2)
            if((rx[j]^intermediate[j]) & (1ull<<(40+i)))
                f(_xor,j,3);
        rep(j,0,2)
            if((rx[j]^intermediate[j]) & (1ull<<(24+i)))
                f(_xor,j,3,l32);
        rep(j,0,2)
            if((rx[j]^intermediate[j]) & (1ull<<(8+i)))
                f(_xor,j,3,u8,u8);
        rep(j,0,2)
            if((rx[j]^intermediate[j]) & (1ull<<(i)))
                f(_xor,j,3,l8,u8);
        f(_add,3,3);
    }
    assert(rx[3] == m);
    rep(j,0,2)
        f(_mul,j,3);
    make_rx3_rem();
    f(_inc,3);
    rep(i,0,7){
        rep(j,0,2)
            if((rx[j]^goal[j]) & (1ull<<(32+i)))
                f(_xor,j,3);
        rep(j,0,2)
            if((rx[j]^goal[j]) & (1ull<<(16+i)))
                f(_xor,j,3,l32);
        rep(j,0,2)
            if((rx[j]^goal[j]) & (1ull<<(8+i)))
                f(_xor,j,3,u8,l8);
        rep(j,0,2)
            if((rx[j]^goal[j]) & (1ull<<(i)))
                f(_xor,j,3,l8,l8);
        f(_add,3,3);
    }
}
ll mock(void (*to_test)(vull), vull initial, vull goal){
    auto old_saving = saving;
    saving = false;
    int old_op = cnt_op;
    save_state();
    rep(i,0,sz(initial)-1)
        rx[i] = initial[i];
    to_test(goal);
    load_state();
    saving = old_saving;
    int ans = cnt_op-old_op;
    cnt_op = old_op;
    return ans;
}
template<typename T>
ll mock(void (*to_test)(T), T goals){
    saving = false;
 
    int old_op = cnt_op;
    vull _state = get_state();
    to_test(goals);
    set_state(_state);
    saving = true;
    int ans = cnt_op-old_op;
    cnt_op = old_op;
    return ans;
}
vull best_permute(void (*)(vull), vull);
vvull rand_permute(void (*)(vvull), vvull, int);
void tsp_permute(void (*)(vull), vvull&);
void outer16(vvull goals){
    rep(t,0,n-1){
        vull goal = best_permute(inner16,goals[t]);
        inner16(goal);
        rep(j,0,2) assert((rx[j]^goal[j])==0);
    }
}
void calc_dist(void (*to_test)(vull), vvull goals){
    vull state = get_state();
    rep(i,0,sz(goals)-1)
        rep(j,0,sz(goals)-1){
            set_state(goals[i]);
            dist[i][j] = mock(to_test,get_state(),best_permute(to_test,goals[j]));
        }
    set_state(state);
}
bool visited[64];
vi path;
int cost = 0;
void dfs(int u, int sz){
    visited[u] = true;
    path.pb(u);
    if(sz(path) == sz)
        return;
    vpii best_cont;
    rep(v,0,sz-1)
        if(!visited[v])
            best_cont.pb({dist[u][v],v});
    sort(all(best_cont));
    for(auto _ : best_cont){
        if(sz(path) < 50 && rand()%15 == 0) continue;
        cost += _.X;
        dfs(_.Y,sz);
        if(sz(path) == sz)
            return;
        cost -= _.X;
    }
    if(sz(path) == sz)
        return;
    visited[u] = false;
    path.pop_back();
    return;
}
vi mst_order(int sz = 64){
    vvi edges;
    rep(i,0,sz-1)
        rep(j,i+1,sz-1)
            edges.pb({dist[i][j],i,j});
    DSU dsu(sz);
    vi deg(sz);
    vvi adj(sz);
    ll cost = 0;
    for(auto _ : edges){
        int u = _[1];
        int v = _[2];
        if(deg[u] <= 1 && deg[v] <= 1 && dsu.unite(u,v)){
            ++deg[u];
            ++deg[v];
            adj[u].pb(v);
            adj[v].pb(u);
            cost += _[0];
        }
    }
    int start = 0;
    while(deg[start] != 1)
        ++start;
    vi ans(1,start);
    rep(i,0,sz(ans)-1){
        int u = ans[i];
        for(int v : adj[u]){
            if(deg[v] != 0){
                ans.pb(v);
                deg[u]--;
                deg[v]--;
            }
        }
    }
    watch(cost);
    watch(sz(ans));
    return ans;
 
}
vi mf_order(int sz = 64){
    vvi edges;
    rep(i,0,sz-1)
        rep(j,i+1,sz-1)
            edges.pb({dist[i][j],i,j});
    DSU dsu(sz);
    vi deg(sz);
    ll cost = 0;
    ll icost = 0;
    vi ls,rs;
    for(auto _ : edges){
        int u = _[1];
        int v = _[2];
        if(deg[u] <= 0 && deg[v] <= 0 && dsu.unite(u,v)){
            ++deg[u];
            ++deg[v];
            icost += _[0];
            ls.pb(u);
            rs.pb(v);
        }
    }
    ll tcost = MOD;
    rep(times,0,1000){
        cost = icost;
        rep(i,0,31)
            if(rand()%2)
                swap(ls[i],rs[i]);
        MaxFlow<int> mf;
        vvi edge_indices(32,vi(32));
        rep(i,0,31)
            rep(j,0,31)
                edge_indices[i][j] = mf.add_edge(ls[i],rs[j],1,dist[ls[i]][rs[j]]);
        int ts = -1;
        rep(i,0,31)
            mf.add_edge(ts,ls[i],1,0);
        rep(j,0,31)
            mf.add_edge(rs[j],mf.sink,1,0);
        mf.add_edge(mf.source,ts,31,0);
        cost += mf.min_cost_flow().Y;
        tcost = min(tcost,cost);
    }
    watch(tcost);
    return {};
}
vi decent_order(int sz = 64){
    vi best_path; 
    int best_cost = MOD;
    rep(start,0,30*(sz-1)){
        cost = 0;
        path.clear();
        memset(visited,0,sizeof visited);
        dfs(start%sz,sz);
        if(cost < best_cost){
            best_path = path;
            best_cost = cost;
        }
    }
    return best_path;
}
void set_order(vvull &goals, vi order){
    vvull b(sz(goals));
    rep(i,0,sz(goals)-1)
        b[i] = goals[order[i]];
    goals = b;
}
void solve16(){
    f(_inc,3,u8); //8
    f(_mov,0,3);
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    f(_inc,3,u8); //32,8
    f(_mul,3,3,l32); //32,16
    f(_inc,3); //32,16,0
    f(_mul,3,0); //40,24,8
    vvull goals = a;
    tsp_permute(inner16,goals);
 
    outer16(goals);
}
 
void inner56(int t, vull goal){
    if(t > 0){
        f(_add,2,0);
        f(_add,2,1);
    }
    {
        int endp = 1+(t==0);
        vull intermediate(3);
        ull m = (ull(1)<<48)+(ull(1)<<32)+(ull(1)<<16);
        rep(i,0,endp){
            try{
                intermediate[i] = choose(rx[i],goal[i]);
            }catch(...){
                f(_sub,i,i);
                intermediate[i] = choose(rx[i],goal[i]);
            }
        }
        rep(i,0,7){
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(40+i)))
                    f(_xor,j,3);
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(24+i)))
                    f(_xor,j,3,l32);
            rep(j,0,endp){
                if((rx[j]^intermediate[j]) & (1ull<<(8+i)))
                    f(_xor,j,3,u8,u8);
            }
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(i)))
                    f(_xor,j,3,l8,u8);
            f(_add,3,3);
        }
        assert(rx[3] == m);
        rep(j,0,endp)
            f(_mul,j,3);
        make_rx3_rem();
        f(_inc,3);
        rep(i,0,7){
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(32+i)))
                    f(_xor,j,3);
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(16+i)))
                    f(_xor,j,3,l32);
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(8+i)))
                    f(_xor,j,3,u8,l8);
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(i)))
                    f(_xor,j,3,l8,l8);
            f(_add,3,3);
        }
        if(t > 0){
            f(_sub,2,0);
            f(_sub,2,1);
        }
    }
}
void inner56_init(vull goal){
    inner56(0,goal);
}
void inner56_normal(vull goal){
    inner56(1,goal);
}
void outer56(vvull goals){
    rep(t,0,n-1){
        auto func = t == 0 ? inner56_init : inner56_normal;
        vull goal = goals[t];
        goal = best_permute(func,goals[t]);
        func(goal);
        rep(j,0,2) assert((rx[j]^goal[j])==0);
    }
}
void solve56(){
    f(_inc,3,u8); //8
    f(_mov,0,3);
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    f(_inc,3,u8); //32,8
    f(_mul,3,3,l32); //32,16
    f(_inc,3); //32,16,0
    f(_mul,3,0); //40,24,8
    vvull goals = a;
    tsp_permute(inner56_normal,goals);
    outer56(goals);
}
void inner4(vull goal){
    rep(times,0,3){
        if(times > 2){
            if(goal[0]>>32 != rx[0]>>32){
                     if(goal[0]>>32 == g(_add,0,1)>>32) f(_add,    0,1);
                else if(goal[0]>>32 == g(_xor,0,1)>>32) f(_xor,    0,1);
                else if(goal[0]>>32 == g(_sub,0,1)>>32) f(_sub,    0,1);
                else if(goal[0]>>32 == g(_and,0,1)>>32) f(_and,    0,1);
                else if(goal[0]>>32 == g(_or, 0,1)>>32) f(_or,     0,1);
                else if(goal[0]>>32 == g(_add,0,2)>>32) f(_add,    0,2);
                else if(goal[0]>>32 == g(_xor,0,2)>>32) f(_xor,    0,2);
                else if(goal[0]>>32 == g(_sub,0,2)>>32) f(_sub,    0,2);
                else if(goal[0]>>32 == g(_and,0,2)>>32) f(_and,    0,2);
                else if(goal[0]>>32 == g(_or, 0,2)>>32) f(_or,     0,2);
                else if(times>1 && goal[0]>>32 == g(_mov,0,1)>>32) f(_mov,    0,1);
                else if(times>1 && goal[0]>>32 == g(_mov,0,2)>>32) f(_mov,    0,2);
            }
            if(goal[1]>>32 != rx[1]>>32){
                     if(goal[1]>>32 == g(_add,1,0)>>32) f(_add,    1,0);
                else if(goal[1]>>32 == g(_xor,1,0)>>32) f(_xor,    1,0);
                else if(goal[1]>>32 == g(_sub,1,0)>>32) f(_sub,    1,0);
                else if(goal[1]>>32 == g(_and,1,0)>>32) f(_and,    1,0);
                else if(goal[1]>>32 == g(_or, 1,0)>>32) f(_or,     1,0);
                else if(goal[1]>>32 == g(_add,1,2)>>32) f(_add,    1,2);
                else if(goal[1]>>32 == g(_xor,1,2)>>32) f(_xor,    1,2);
                else if(goal[1]>>32 == g(_sub,1,2)>>32) f(_sub,    1,2);
                else if(goal[1]>>32 == g(_and,1,2)>>32) f(_and,    1,2);
                else if(goal[1]>>32 == g(_or, 1,2)>>32) f(_or,     1,2);
                else if(times > 1 && goal[1]>>32 == g(_mov,1,0)>>32) f(_mov,    1,0);
                else if(times > 1 && goal[1]>>32 == g(_mov,1,2)>>32) f(_mov,    1,2);
            }
            if(goal[0]>>32 != rx[0]>>32){
                     if(goal[2]>>32 == g(_add,2,1)>>32) f(_add,    2,1);
                else if(goal[2]>>32 == g(_xor,2,1)>>32) f(_xor,    2,1);
                else if(goal[2]>>32 == g(_sub,2,1)>>32) f(_sub,    2,1);
                else if(goal[2]>>32 == g(_and,2,1)>>32) f(_and,    2,1);
                else if(goal[2]>>32 == g(_or, 2,1)>>32) f(_or,     2,1);
                else if(goal[2]>>32 == g(_add,2,0)>>32) f(_add,    2,0);
                else if(goal[2]>>32 == g(_xor,2,0)>>32) f(_xor,    2,0);
                else if(goal[2]>>32 == g(_sub,2,0)>>32) f(_sub,    2,0);
                else if(goal[2]>>32 == g(_and,2,0)>>32) f(_and,    2,0);
                else if(goal[2]>>32 == g(_or, 2,0)>>32) f(_or,     2,0);
                else if(times > 1 && goal[2]>>32 == g(_mov,2,1)>>32) f(_mov,    2,1);
                else if(times > 1 && goal[2]>>32 == g(_mov,2,0)>>32) f(_mov,    2,0);
            }
        }
        if(goal[0] != rx[0]){
            if(goal[0] == g(_add,0,1)) f(_add,    0,1);
            else if(goal[0] == g(_xor,0,1)) f(_xor,    0,1);
            else if(goal[0] == g(_sub,0,1)) f(_sub,    0,1);
            else if(goal[0] == g(_and,0,1)) f(_and,    0,1);
            else if(goal[0] == g(_or, 0,1)) f(_or,     0,1);
            else if(goal[0] == g(_add,0,1,l32)) f(_add,0,1,l32);
            else if(goal[0] == g(_xor,0,1,l32)) f(_xor,0,1,l32);
            else if(goal[0] == g(_sub,0,1,l32)) f(_sub,0,1,l32);
            else if(goal[0] == g(_and,0,1,l32)) f(_and,0,1,l32);
            else if(goal[0] == g(_or, 0,1,l32)) f(_or, 0,1,l32);
            else if(goal[0] == g(_add,0,2)) f(_add,    0,2);
            else if(goal[0] == g(_xor,0,2)) f(_xor,    0,2);
            else if(goal[0] == g(_sub,0,2)) f(_sub,    0,2);
            else if(goal[0] == g(_and,0,2)) f(_and,    0,2);
            else if(goal[0] == g(_or, 0,2)) f(_or,     0,2);
            else if(goal[0] == g(_add,0,2,l32)) f(_add,0,2,l32);
            else if(goal[0] == g(_xor,0,2,l32)) f(_xor,0,2,l32);
            else if(goal[0] == g(_sub,0,2,l32)) f(_sub,0,2,l32);
            else if(goal[0] == g(_and,0,2,l32)) f(_and,0,2,l32);
            else if(goal[0] == g(_or, 0,2,l32)) f(_or, 0,2,l32);
            else if(times > 0 && goal[0] == g(_mov,0,1)) f(_mov,    0,1);
            else if(times > 0 && goal[0] == g(_mov,0,2)) f(_mov,    0,2);
            else if(times > 0 && goal[0] == g(_mov,0,1,l32)) f(_mov,0,1,l32);
            else if(times > 0 && goal[0] == g(_mov,0,2,l32)) f(_mov,0,2,l32);
        }
        if(goal[1] != rx[1]){
            if(goal[1] == g(_add,1,0)) f(_add,    1,0);
            else if(goal[1] == g(_xor,1,0)) f(_xor,    1,0);
            else if(goal[1] == g(_sub,1,0)) f(_sub,    1,0);
            else if(goal[1] == g(_and,1,0)) f(_and,    1,0);
            else if(goal[1] == g(_or, 1,0)) f(_or,     1,0);
            else if(goal[1] == g(_add,1,0,l32)) f(_add,1,0,l32);
            else if(goal[1] == g(_xor,1,0,l32)) f(_xor,1,0,l32);
            else if(goal[1] == g(_sub,1,0,l32)) f(_sub,1,0,l32);
            else if(goal[1] == g(_and,1,0,l32)) f(_and,1,0,l32);
            else if(goal[1] == g(_or, 1,0,l32)) f(_or, 1,0,l32);
            else if(goal[1] == g(_add,1,2)) f(_add,    1,2);
            else if(goal[1] == g(_xor,1,2)) f(_xor,    1,2);
            else if(goal[1] == g(_sub,1,2)) f(_sub,    1,2);
            else if(goal[1] == g(_and,1,2)) f(_and,    1,2);
            else if(goal[1] == g(_or, 1,2)) f(_or,     1,2);
            else if(goal[1] == g(_add,1,2,l32)) f(_add,1,2,l32);
            else if(goal[1] == g(_xor,1,2,l32)) f(_xor,1,2,l32);
            else if(goal[1] == g(_sub,1,2,l32)) f(_sub,1,2,l32);
            else if(goal[1] == g(_and,1,2,l32)) f(_and,1,2,l32);
            else if(goal[1] == g(_or, 1,2,l32)) f(_or, 1,2,l32);
            else if(times > 0 && goal[1] == g(_mov,1,0)) f(_mov,    1,0);
            else if(times > 0 && goal[1] == g(_mov,1,2)) f(_mov,    1,2);
            else if(times > 0 && goal[1] == g(_mov,1,0,l32)) f(_mov,1,0,l32);
            else if(times > 0 && goal[1] == g(_mov,1,2,l32)) f(_mov,1,2,l32);
        }
        if(goal[2] != rx[2]){
            if(goal[2] == g(_add,2,0)) f(_add,    2,0);
            else if(goal[2] == g(_xor,2,0)) f(_xor,    2,0);
            else if(goal[2] == g(_sub,2,0)) f(_sub,    2,0);
            else if(goal[2] == g(_and,2,0)) f(_and,    2,0);
            else if(goal[2] == g(_or, 2,0)) f(_or,     2,0);
            else if(goal[2] == g(_add,2,0,l32)) f(_add,2,0,l32);
            else if(goal[2] == g(_xor,2,0,l32)) f(_xor,2,0,l32);
            else if(goal[2] == g(_sub,2,0,l32)) f(_sub,2,0,l32);
            else if(goal[2] == g(_and,2,0,l32)) f(_and,2,0,l32);
            else if(goal[2] == g(_or, 2,0,l32)) f(_or, 2,0,l32);
            else if(goal[2] == g(_add,2,1)) f(_add,    2,1);
            else if(goal[2] == g(_xor,2,1)) f(_xor,    2,1);
            else if(goal[2] == g(_sub,2,1)) f(_sub,    2,1);
            else if(goal[2] == g(_and,2,1)) f(_and,    2,1);
            else if(goal[2] == g(_or, 2,1)) f(_or,     2,1);
            else if(goal[2] == g(_add,2,1,l32)) f(_add,2,1,l32);
            else if(goal[2] == g(_xor,2,1,l32)) f(_xor,2,1,l32);
            else if(goal[2] == g(_sub,2,1,l32)) f(_sub,2,1,l32);
            else if(goal[2] == g(_and,2,1,l32)) f(_and,2,1,l32);
            else if(goal[2] == g(_or, 2,1,l32)) f(_or, 2,1,l32);
            else if(times > 0 && goal[2] == g(_mov,2,0)) f(_mov,    2,0);
            else if(times > 0 && goal[2] == g(_mov,2,1)) f(_mov,    2,1);
            else if(times > 0 && goal[2] == g(_mov,2,0,l32)) f(_mov,2,0,l32);
            else if(times > 0 && goal[2] == g(_mov,2,1,l32)) f(_mov,2,1,l32);
        }
    }
    vull t64(3);
    vull t32(3);
    rep(j,0,2){
        t64[j] = (goal[j]^rx[j])>>32;
        goal[j] ^= t64[j];
        t32[j] = ((goal[j]^rx[j])<<32)>>32;
        goal[j] ^= t64[j];
    }
    rep(j,0,2){
        if(bits(t64[j]) > 16){
            f(_not,j);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        if(bits(t32[j]) > 16){
            f(_not,j,l32);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        if(bits(t32[j]&0xffff) > 8 && bits(t32[j]&0x00ff) > 4 && bits(t32[j]&0xff00) > 4){
            f(_not,j,l16);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        if(bits(t32[j]&0x00ff) > 4){
            f(_not,j,l8);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        if(bits(t32[j]&0xff00) > 4){
            f(_not,j,u8);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
    }
    if(vull(rx,rx+3) == goal) return;
    f(_inc,3); //32,1
    rep(i,0,31){
        rep(j,0,2){
            if(t64[j]&rx[3]) f(_xor,j,3);
            if(t32[j]&rx[3]) f(_xor,j,3,l32);
        }
        f(_add,3,3);
    }
    rep(j,0,2)
        assert(rx[j] == goal[j]);
}
void outer4(vvull goals){
    rep(t,0,n-1){
        vull goal = goals[t];
        goal = best_permute(inner4,goals[t]);
        inner4(goal);
    }
}
//void solve4(){
    //f(_inc,3,u8); //8
    //f(_mul,3,3); //16
    //f(_mul,3,3); //32
    //vvull goals = a;
    //tsp_permute(inner4,goals);
    //outer4(goals);
//}
 
 
vull apply_oper(bool keep_changes, int bm){
    vull old_vals(rx,rx+3);
    if(!keep_changes)
        saving = false;
    rep(j,0,2){
        int p1 = bm%3; bm /= 3;
        int p2 = bm%2; bm /= 2;
        if(p2 == p1) p2 = 2;
        int op_index, nr_bits;
        op_index = bm%5; bm /= 5;
        nr_bits = bm%2; bm /= 2;
        if(nr_bits == 0){
            if(op_index == 0) f(_add,p1,p2);
            if(op_index == 1) f(_xor,p1,p2);
            if(op_index == 2) f(_and,p1,p2);
            if(op_index == 3) f(_or,p1,p2);
            if(op_index == 4) f(_sub,p1,p2);
        }
        else{
            if(op_index == 0) f(_add,p1,p2,l32);
            if(op_index == 1) f(_xor,p1,p2,l32);
            if(op_index == 2) f(_and,p1,p2,l32);
            if(op_index == 3) f(_or,p1,p2,l32);
            if(op_index == 4) f(_sub,p1,p2,l32);
        }
 
    }
    vull ret(rx,rx+3);
    if(!keep_changes){
        saving = true;
        rep(j,0,2)
            rx[j] = old_vals[j];
    }
    sort(all(ret));
    return ret;
}
void solve4(){
    f(_inc,3);
    rep(i,0,63){
        rep(j,0,2)
            if(a[0][j]&(1LL<<i))
                f(_xor,j,3);
        f(_add,3,3);
    }
    rep(i,1,n-1){
        sort(all(a[i]));
        saving = false;
        vull old_vals(rx,rx+3);
        //assert(old_vals == a[i-1]);
        int correct_mask = -1;
        rep(bm,0,ipow(60,3))
            if(apply_oper(false,bm) == a[i]){
                correct_mask = bm;
                break;
            }
        assert(correct_mask != -1);
        apply_oper(true,correct_mask);
        set<ull> tmp(rx,rx+4);
        rep(j,0,2) assert(tmp.count(a[i][j]));
    }
}
void inner2(vull goal){
    goal[2] ^= goal[0];
    goal[1] ^= goal[0];
    f(_inc,3); //32,1
    if(rx[1] != 0) f(_sub,1,1);
    if(rx[2] != 0) f(_sub,2,2);
    vull t64(3);
    vull t32(3);
    rep(j,0,2){
        t64[j] = (goal[j]^rx[j])>>32;
        goal[j] ^= t64[j];
        t32[j] = ((goal[j]^rx[j])<<32)>>32;
        goal[j] ^= t64[j];
    }
    rep(j,0,2){
        if(bits(t64[j]) > 16){
            f(_not,j);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        if(bits(t32[j]) > 16){
            f(_not,j,l32);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
 
        int types = 0;
        if(bits(t32[j]&0x00ff) > 4) types ^= 1;
        if(bits(t32[j]&0xff00) > 4) types ^= 2;
        if((types&3)==3){
            f(_not,j,l16);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        else if(types&1){
            f(_not,j,l8);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
        else if(types&2){
            f(_not,j,u8);
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
            goal[j] ^= t64[j];
        }
    }
    rep(i,0,31){
        rep(j,0,2){
            if(t64[j]&rx[3]) f(_xor,j,3);
            if(t32[j]&rx[3]) f(_xor,j,3,l32);
        }
        f(_add,3,3);
    }
    f(_xor,1,0);
    f(_xor,2,0);
}
void outer2(vvull goals){
    rep(t,0,n-1){
        vull goal = best_permute(inner2,goals[t]);
        inner2(goal);
    }
}
void solve2(){
    f(_inc,3,u8); //8
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    vvull goals = a;
    tsp_permute(inner2,goals);
    outer2(goals);
}
void solve26(){
    f(_inc,3,u8); //8
    f(_mov,0,3);
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    f(_inc,3,u8); //32,8
    f(_mul,3,3,l32); //32,16
    f(_inc,3); //32,16,0
    f(_mul,3,0); //40,24,8
    rep(t,0,n-1){
        if(t > 0){
            f(_sub,1,1);
            f(_sub,2,2);
        }
        vull goal = a[t];
        goal[1] ^= goal[0];
        goal[2] ^= goal[0];
        {
            vull intermediate(3);
            ull m = (ull(1)<<48)+(ull(1)<<32)+(ull(1)<<16);
            rep(i,0,2){
                try{
                    intermediate[i] = choose(rx[i],goal[i]);
                }catch(...){
                    f(_sub,i,i);
                    intermediate[i] = choose(rx[i],goal[i]);
                }
            }
            rep(i,0,7){
                rep(j,0,2)
                    if((rx[j]^intermediate[j]) & (1ull<<(40+i)))
                        f(_xor,j,3);
                rep(j,0,2)
                    if((rx[j]^intermediate[j]) & (1ull<<(24+i)))
                        f(_xor,j,3,l32);
                rep(j,0,2)
                    if((rx[j]^intermediate[j]) & (1ull<<(8+i)))
                        f(_xor,j,3,u8,u8);
                rep(j,0,2)
                    if((rx[j]^intermediate[j]) & (1ull<<(i)))
                        f(_xor,j,3,l8,u8);
                f(_add,3,3);
            }
            assert(rx[3] == m);
            rep(j,0,2)
                f(_mul,j,3);
            make_rx3_rem();
            f(_inc,3);
            rep(i,0,7){
                rep(j,0,2)
                    if((rx[j]^goal[j]) & (1ull<<(32+i)))
                        f(_xor,j,3);
                rep(j,0,2)
                    if((rx[j]^goal[j]) & (1ull<<(16+i)))
                        f(_xor,j,3,l32);
                rep(j,0,2)
                    if((rx[j]^goal[j]) & (1ull<<(8+i)))
                        f(_xor,j,3,u8,l8);
                rep(j,0,2)
                    if((rx[j]^goal[j]) & (1ull<<(i)))
                        f(_xor,j,3,l8,l8);
                f(_add,3,3);
            }
            rep(j,0,2) assert((rx[j]^goal[j])==0);
        }
        f(_xor,1,0);
        f(_xor,2,0);
    }
}
void solve5(){
    f(_inc,3,u8); //8
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    rep(t,0,n-1){
        if(t > 0){
            f(_add,2,0);
            f(_add,2,1);
        }
        f(_inc,3); //32,1
        vull goal = a[t];
        vull t64(3);
        vull t32(3);
        rep(j,0,2){
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
        }
        rep(i,0,31){
            rep(j,0,1+(t==0)){
                if(t64[j]&rx[3]) f(_xor,j,3);
                if(t32[j]&rx[3]) f(_xor,j,3,l32);
            }
            f(_add,3,3);
        }
 
        if(t > 0){
            f(_sub,2,0);
            f(_sub,2,1);
        }
    }
}
bool comp(const vull &a, const vull &b){
    return a[1]-a[0] < b[1]-b[0];
}
void solve3(){
    sort(all(a),comp);
    f(_inc,3,u8); //8
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    rep(t,0,n-1){
        f(_inc,3); //32,1
        vull goal = a[t];
        vull t64(3);
        vull t32(3);
        if(t%8)
            f(_sub,2,1);
        rep(j,0,2){
            t64[j] = (goal[j]^rx[j])>>32;
            goal[j] ^= t64[j];
            t32[j] = ((goal[j]^rx[j])<<32)>>32;
        }
        rep(i,0,31){
            rep(j,0,2*(t%8 == 0)){
                if(t64[j]&rx[3]) f(_xor,j,3);
                if(t32[j]&rx[3]) f(_xor,j,3,l32);
            }
            f(_add,3,3);
        }
        if(t%8){
            f(_mov,1,0);
            f(_add,1,2);
            f(_add,2,1);
        }
    }
}
void inner36_8(vull goal, int t2){
    sort(all(goal));
    if(t2)
        f(_sub,2,1);
    {
        int endp = 0+2*(t2 == 0);
        vull intermediate(3);
        ull m = (ull(1)<<48)+(ull(1)<<32)+(ull(1)<<16);
        rep(i,0,endp){
            try{
                intermediate[i] = choose(rx[i],goal[i]);
            }catch(...){
                f(_sub,i,i);
                intermediate[i] = choose(rx[i],goal[i]);
            }
        }
        rep(i,0,7){
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(40+i)))
                    f(_xor,j,3);
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(24+i)))
                    f(_xor,j,3,l32);
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(8+i)))
                    f(_xor,j,3,u8,u8);
            rep(j,0,endp)
                if((rx[j]^intermediate[j]) & (1ull<<(i)))
                    f(_xor,j,3,l8,u8);
            f(_add,3,3);
        }
        assert(rx[3] == m);
        rep(j,0,endp)
            f(_mul,j,3);
        make_rx3_rem();
        f(_inc,3);
        rep(i,0,7){
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(32+i)))
                    f(_xor,j,3);
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(16+i)))
                    f(_xor,j,3,l32);
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(8+i)))
                    f(_xor,j,3,u8,l8);
            rep(j,0,endp)
                if((rx[j]^goal[j]) & (1ull<<(i)))
                    f(_xor,j,3,l8,l8);
            f(_add,3,3);
        }
 
        if(t2){
            f(_mov,1,0);
            f(_add,1,2);
            f(_add,2,1);
        }
        rep(j,0,2) assert((rx[j]^goal[j])==0);
    }
}
void inner36_8_0(vull goal){
    inner36_8(goal,0);
}
void inner36_8_1(vull goal){
    inner36_8(goal,1);
}
void outer36(vvull goals){
    rep(t2,0,7){
        if(t2 == 0){
            goals[t2] = best_permute(inner36_8_0,goals[t2]);
            inner36_8_0(goals[t2]);
        }
        else{
            goals[t2] = best_permute(inner36_8_1,goals[t2]);
            inner36_8_1(goals[t2]);
        }
    }
}
void far_out36(vector<vvull> goals){
    rep(i,0,7)
        outer36(goals[i]);
}
void solve36(){
    sort(all(a),comp);
    f(_inc,3,u8); //8
    f(_mov,0,3);
    f(_mul,3,3); //16
    f(_mul,3,3); //32
    f(_inc,3,u8); //32,8
    f(_mul,3,3,l32); //32,16
    f(_inc,3); //32,16,0
    f(_mul,3,0); //40,24,8
    vvull goals = a;
    vector<vvull> buckets(8),best;
    rep(i,0,7){
        buckets[i] = vvull(goals.begin()+i*8,goals.begin()+(i+1)*8);
        tsp_permute(inner36_8_1,buckets[i]);
    }
    best = buckets;
    int best_cost = MOD;
    rep(attempts,0,400){
        ll cur_cost = mock(far_out36,buckets);
        if(cur_cost < best_cost){
            best_cost = cur_cost;
            best = buckets;
        }
        random_shuffle(all(buckets));
    }
    far_out36(buckets);
}
    //if(!keep_changes)
 
    //if(!keep_changes){
void _(){
    ll total = 0;
    ll display = 0;
    int cnt = 0;
    while(cin >> n){
        ++cnt;
        if(cnt > 5)
            break;
        a = vvull(n,vull(3)); cin >> a;
        type = get_type();
        if(type != 4){
            for(auto &_ : a)
                sort(all(_));
            sort(all(a));
        }
        //if(type != 2) continue;
        if(type == 4)
            solve4();
        else if(type == 2)
            solve2();
        else if(type == 3)
            solve36();
        else if(type == 5)
            solve56();
        else
            solve16();
        check(a);
        //assert(type != 1);
        if(type == 1){
        }
        cerr << type << ' ' << sz(description) << '\n';;
        print(sz(description));
        print(description,"\n");
        total += sz(description);
        if(type == 2 || type == 4 || type == 5)
            display += sz(description);
        description.clear();
        memset(rx,0,sizeof rx);
    }
    watch(total);
    watch(display/2);
}
void tsp_permute(void (*to_test)(vull), vvull &goals){
    calc_dist(to_test,goals);
    vi order;
    if(sz(goals) > 8){
        order = decent_order(sz(goals));
    }
    else{
        vi ans(8);
        iota(all(ans),0);
        vi best;
        int best_cost = MOD;
        do{
            ll cur_cost = 0;
            rep(i,1,7)
                cur_cost += dist[ans[i-1]][ans[i]];
            if(cur_cost < best_cost){
                best_cost = cur_cost;
                best = ans;
            }
        }while(next_permutation(all(ans)));
        order = best;
    }
    set_order(goals,order);
}
vvull rand_permute(void (*to_test)(vvull), vvull goals, int rand_times){
    sort(all(goals));
    vvull best = goals;
    int best_cost = MOD;
    rep(attempts,0,rand_times){
        int cur_cost = mock(to_test,goals);
        if(cur_cost < best_cost){
            best_cost = cur_cost;
            best = goals;
        }
        random_shuffle(all(goals));
    }
    return best;
}
vull best_permute(void (*to_test)(vull), vull goal){
    sort(all(goal));
    vull best = goal;
    int best_cost = MOD;
    do{
        int cur_cost = mock(to_test,get_state(),goal);
        if(cur_cost < best_cost){
            best_cost = cur_cost;
            best = goal;
        }
    }while(next_permutation(all(goal)));
    return best;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        _();
}