#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);
}

bitset<MAXN> vis;

vector<int> Resi(int N, int Q){
    n = N;
    vector<int> p(n+1);
    vector<int> v1,v2;
    while(true){
        int x = rng()%n+1;
        int y = rng()%n+1;
        int z = rng()%n+1;
        if(x == y || y == z || x == z) continue;
        if(Pitaj(x,y,z) == 0){
            v1 = {x,y,z};
            vis[x] = vis[y] = vis[z] = 1;
            break;
        }
    }
    for(int i = 1; i <= n; ++i){
        if(vis[i]) continue;
        if(Pitaj(v1[0],v1[1],i) == 0) v1.push_back(i);
        else v2.push_back(i);
        vis[i] = 1;
    }
    if(v1.size() < v2.size()) swap(v1,v2);
    //for(int k : v1) cout << k << ' '; cout << '\n';
    //for(int k : v2) cout << k << ' '; cout << '\n';
    bg = v2[0];
    pivot(v1,1);
    bg = v1[0];
    pivot(v2,v1.size()+1);
    reverse(a+n/2+2, a+n+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;
}