#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include "code.h"

using namespace std;
#define pb push_back

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

int p = 0;
vector<int> a;
mt19937 rng(time(0));
void solve(int l, int r, vector<int> &v) {
    if (v.empty())  return;
    int n = v.size();
    vector<int> L, R;
    for (int i = 0; i < n-1; ++i) {
        //cout << v[i] << ' ' << v[n-1] << ' ' << p << endl;
        if (Pitaj(p, v[n-1], v[i]) == -1) {
            //cout << i << '\n';
            L.pb(v[i]);
        }
        else {
            //cout << i << '\n';
            R.pb(v[i]);
        }
    }
    a[v[n-1]] = L.size()+l;
    solve(l, l+L.size()-1, L);
    solve(l+L.size()+1, r, R);
}
vector<int> Resi(int n, int q){
    a.resize(n+1);
    for (int i = 1; i+2 <= n; i+=3) {
        int x = Pitaj(i, i+1, i+2);
        if (x) {
            int z = (i == 1 ? n : 1);
            if (!Pitaj(i, i+1, z)) {
                p = i+2;
                break;
            }
            if (!Pitaj(i, i+2, z)) {
                p = i+1;
                break;
            }
            else {
                p = i;
            }
        }
        if (i+5 > n) {
            i -= 2;
        }
    }
    //cout << p << endl;
    vector<int> v;
    a[p] = n;
    for (int i = 1; i <= n; ++i) {
        if (i != p) v.pb(i);
    }
    for (int i = 0; i < n-1; ++i)   swap(v[i], v[rng()%(i+1)]);
    solve(1, n-1, v);
    return a;
}