#include <bits/stdc++.h>
#include "code.h"

vector<pair<int, int>> ZapisiTacke(int n){
    vector<pair<int, int>> r(n+1, make_pair(0, 0));
    for(int i = 1; i < n+1; i++){
        r[i].first = i;
    }
    r[1].second = 1;

    return r;
}

vector<int> Resi(int n, int q){
    vector<int> p(n+1, 0);
    int k1 = 0, k2 = 0, k3 = 0, l1 = 0, l2 = 0, l3 = 0;

    int i = 1;
    while(k1*k2*k3*l1*l2*l3 == 0){
        if(i+2 > n) i -= (i+2)-n;

        int vr = Pitaj(i, i+1, i+2);
        if(vr == 0){
            l1 = i;
            l2 = i+1;
            l3 = i+2;
        }
        else{
            k1 = i;
            k2 = i+1;
            k3 = i+2;
        }
        i+=3;
    }

    if(Pitaj(k2, l1, l2) != 0) k1 = k2;
    if(Pitaj(k3, l1, l2) != 0) k1 = k3;

    p[k1] = 1;
    //cout << k1 << endl;

    vector<vector<int>> grupe(3*n);
    for(i = 0; i < n; i++){
        grupe[0].push_back(i+1);
    }
    int sl_gr = 1;

    vector<int> a(n+1, 0); //u kojoj je grupi svaki el
    vector<int> b(3*n, 2); //offset grupe

    for(i = 1; i < n+1; i++){
        if(i == k1) continue;
        //cout << i << endl;
        int gr_i = a[i], levo = 0, desno = 0;

        for(int j = 0; j < grupe[gr_i].size(); j++){
            if(grupe[gr_i][j] == i || grupe[gr_i][j] == k1) continue;

            if(Pitaj(i, k1, grupe[gr_i][j]) == 1){
                levo++;
                grupe[sl_gr].push_back(grupe[gr_i][j]);
                a[grupe[gr_i][j]] = sl_gr;
            }
            else{
                desno++;
                grupe[sl_gr+1].push_back(grupe[gr_i][j]);
                a[grupe[gr_i][j]] = sl_gr+1;
            }
        }

        b[sl_gr] = b[gr_i];
        b[sl_gr+1] = b[gr_i]+levo+1;
        p[i] = levo+b[gr_i];

        sl_gr+= 2;
    }

    return p;
}