#include <bits/stdc++.h>
#include "code.h"
using namespace std;
const int MAXN = 1005;


int n;
mt19937 rng(time(nullptr));

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

int bg;
int a[MAXN];

void pivot(vector<int> v, int of){
    if(v.size() == 1){
        a[of] = v[0];
        return;
    }
    if(v.size() == 0) return;
    int idx = rng() % v.size();
    //cout << "pivot "; for(int k : v) cout << k << ' '; cout << '\n';
    vector<int> v1, v2;
    for(int i = 0; i < v.size(); ++i){
        if(i == idx) continue;
        //cout << bg << ' ' << v[idx] << ' ' << v[i] << '\n';
        if(Pitaj(bg,v[idx],v[i]) == 1) v1.push_back(v[i]);
        else v2.push_back(v[i]);
    }
    a[of+v1.size()] = v[idx];
    pivot(v1,of);
    pivot(v2,of+v1.size()+1);
}

vector<int> Resi(int N, int Q){
    n = N;
    vector<int> p(n+1);
    bg = -1;
    for(int i = 1; i+2 <= n; i += 3){
        if(Pitaj(i,i+1,i+2) == 0) continue;
        int tmp = (i == 1 ? n : 1);
        if(Pitaj(i,i+1,tmp) == 0) bg = i+2;
        else if(Pitaj(i,i+2,tmp) == 0) bg = i+1;
        else bg = i;
        break;
    }
    if(bg == -1){
        if(n%3==1) bg = n;
        else{
            if(Pitaj(1,2,n) == 0) bg = n-1;
            else bg = n;
        }
    }
    p[bg] = n;
    vector<int> v;
    for(int i = 1; i <= n; ++i){
        if(i != bg) v.push_back(i);
    }
    //cout << bg << "  "; for(int k : v) cout << k << ' '; cout << '\n';
    pivot(v,1);
    //for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << '\n';
    for(int i = 1; i < n; ++i){
        p[a[i]] = i;
    }
    return p;
}