#include <iostream>
#include <vector>
#include<bits/stdc++.h>
#include "code.h"
#define fi first
#define se second

using namespace std;

mt19937 rng (chrono::steady_clock::now().time_since_epoch().count() );
int n;
int prva;


vector<pair<int, int>> ZapisiTacke(int N){

    vector<pair<int, int>> tacke(N+1);

    tacke[1].fi=0;
    tacke[1].se=0;

    for(int i=2;i<=N;i++){
        tacke[i].se=1;
        tacke[i].fi=i-1;
    }

    return tacke;
}

void poredjaj(vector<int>& p){
    int sz=p.size();
    if(sz==0)return;
    if(sz==1)return;
    int c=p[ rng()%sz ];
    vector<int> levo;
    vector<int> desno;
    for(int i=0;i<sz;i++){
        if(p[i]==c)continue;
        int x=Pitaj(prva,c,p[i]);
        if(x==-1)desno.push_back(p[i]);
        else levo.push_back(p[i]);
    }
    poredjaj(levo);
    poredjaj(desno);
    int szl=levo.size();
    int szd=desno.size();
    for(int i=0;i<szl;i++)p[i]=levo[i];
    p[szl]=c;
    for(int i=0;i<szd;i++)p[i+szl+1]=desno[i];
}

vector<int> Resi(int N, int Q){
    n=N;
    prva=-1;
    vector<int> pot(3);
    for(int i=1;i<=N;i+=3){
        if(i==N){
            pot[0]=N;
            pot[1]=1;
            pot[2]=2;
            break;
        }
        if(i==N-1){
            pot[0]=N;
            pot[1]=N-1;
            pot[2]=1;
            break;
        }
        else{
            int x=Pitaj(i,i+1,i+2);
            //cout<<x<<endl;
            if(x!=0){
                pot[0]=i;
                pot[1]=i+1;
                pot[2]=i+2;
                break;
            }
        }
    }
    int ost=-1;
    if(pot[0]!=1 && pot[1]!=1 && pot[2]!=1)ost=1;
    else if (pot[0]!=2 && pot[1]!=2 && pot[2]!=2)ost=2;
    else if (pot[0]!=3 && pot[1]!=3 && pot[2]!=3)ost=3;
    else ost=4;

    //cout<<pot[0]<<' '<<pot[1]<<' '<<pot[2]<<endl;

    int x=Pitaj(pot[0],pot[1],ost);
    if(x==0)prva=pot[2];
    else{
        x=Pitaj(pot[0],pot[2],ost);
        if(x==0)prva=pot[1];
        else prva=pot[0];
    }
    //cout<<prva<<' '<<ost<<endl;
    vector<int> p;
    for(int i=1;i<=n;i++)if(i!=prva)p.push_back(i);
    poredjaj(p);
    vector<int> v(n+1);
    v[1]=prva;
    for(int i=2;i<=n;i++)v[i]=p[i-2];

    vector<int> ans(n+1);
    for(int i=1;i<=n;i++)ans[v[i]]=i;


    return ans;
}