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

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

int f;

bool A(int a, int b) {
    //cout << a << " " << b << " " << f << endl;
    return (Pitaj(a, b, f) == -1);
}

vector<int> PPV(vector<int> v) {
    int s = v.size(), s1 = s / 2 + s % 2, s2 = s / 2;
    if (s == 1)
        return v;
    vector<int> vl, vr;
    for (int i = 0; i < s; i++) {
        if (i < s1)
            vl.push_back(v[i]);
        else
            vr.push_back(v[i]);
    }
    vl = PPV(vl);
    vr = PPV(vr);
    int l = 0, r = 0;
    vector<int> va;
    while (l != s1 or r != s2) {
        if (l == s1) {
            va.push_back(vr[r]);
            r++;
        } else if (r == s2) {
            va.push_back(vl[l]);
            l++;
        } else {
            if (A(vl[l], vr[r])) {
                va.push_back(vl[l]);
                l++;
            } else {
                va.push_back(vr[r]);
                r++;
            }
        }
    }
    return va;
}

vector<int> Resi(int N, int Q){
    vector<int> res(N+1);
    for (int i = 1; i <= N; i+=3) {
        int a = i, b = i + 1, c = i + 2, d = i + 3;
        if (i == N) {
            b = 1;
            c = 2;
            d = 3;
        } else if (i == N - 1) {
            c = 1;
            d = 2;
        } else if (i == N - 2) {
            d = 1;
        }
        if (Pitaj(a, b, c) == 0)
            continue;
        if (Pitaj(b, c, d) == 0) {
            res[a] = 1;
            f = a;
            break;
        }
        if (Pitaj(a, c, d) == 0) {
            res[b] = 1;
            f = b;
            break;
        }
        if (Pitaj(b, a, d) == 0) {
            res[c] = 1;
            f = c;
            break;
        }
    }
    //cout << f << endl;
    vector<int> v;
    for (int i = 1; i <= N; i++) {
        if (i == f)
            continue;
        v.push_back(i);
    }
    /*for (int x : v)
        cout << x << " ";
    cout << endl;*/
    //sort(v.begin(), v.end(), A);
    v = PPV(v);
    /*for (int x : v)
        cout << x << " ";
    cout << endl;*/
    int c = N;
    for (int i = 0; i < N - 1; i++) {
        //if (c == f)
        //    c--;
        res[v[i]] = c;
        c--;
    }
    return res;
}