#include<bits/stdc++.h>
#include "code.h"
using namespace std;

vector<pair<int, int>> ZapisiTacke(int N){
    vector<pair<int, int>> tacke(N+1);
    for(int i = 1;i<N;i++){
        tacke[i] = {i-N/2, 0};
    }
    tacke[N] = {0, -1};
    return tacke;
}

vector<int> Resi2(vector<int> &t, int in){
    int sz = t.size();
    sz--;
    vector<int> ans(1, 0);
    if(sz==1){
        ans.push_back(t[1]);
        return ans;
    }
    vector<int> t1(1, 0), t2(1, 0);
    for(int i = 1;i<=sz/2;i++){
        t1.push_back(t[i]);
    }
    for(int i = sz/2+1;i<=sz;i++){
        t2.push_back(t[i]);
    }
    t1 = Resi2(t1, in);
    t2 = Resi2(t2, in);
    int sz1 = t1.size(), sz2 = t2.size();
    sz1--;
    sz2--;
    int i = 1, j = 1;
    while((i<=sz1)&&(j<=sz2)){
        int a = Pitaj(t1[i], t2[j], in);
        if(a==-1){
            ans.push_back(t1[i]);
            i++;
        } else{
            ans.push_back(t2[j]);
            j++;
        }
    }
    if(i<=sz1){
        for(int k = i;k<=sz1;k++){
            ans.push_back(t1[k]);
        }
    }
    if(j<=sz2){
        for(int k = j;k<=sz2;k++){
            ans.push_back(t2[k]);
        }
    }
    return ans;
}

vector<int> Resi(int N, int Q){
    vector<int> resenje(N+1);
    //pronalazenje tacke N
    int a = -1;
    for(int i = 1;i+2<=N;i+=3){
        if(Pitaj(i, i+1, i+2)!=0){
            a = i;
        }
    }
    int in = -1;
    if(a==-1){
        a = N-2;
    }
    if(a==1){
        if(Pitaj(a, a+1, a+3)==0){
            in = a+2;
        }
        if(Pitaj(a, a+2, a+3)==0){
            in = a+1;
        }
        if(Pitaj(a+1, a+2, a+3)==0){
            in = a;
        }
    } else{
        if(Pitaj(a, a+1, 1)==0){
            in = a+2;
        }
        if(Pitaj(a, a+2, 1)==0){
            in = a+1;
        }
        if(Pitaj(a+1, a+2, 1)==0){
            in = a;
        }
    }
    resenje[in] = N;
    //sortiranje ostalih
    vector<int> t(N);
    for(int i = 1;i<=N-1;i++){
        if(i<in){
            t[i] = i;
        } else{
            t[i] = i+1;
        }
    }
    vector<int> ans = Resi2(t, in);
    for(int i = 1;i<=N-1;i++){
        resenje[ans[i]] = i;
    }
    return resenje;
}