#include <bits/stdc++.h>
#include "code.h"
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define f first
#define s second
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define vpl vector<pl>
#define vpi vector<pi>
#define sz(x) x.size()
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define F0R(i,a) FOR(i,0,(a))
#define ROF(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define R0F(i,a) ROF(i,0,(a))
#define trav(el, v) for(auto &el : v)
#define nl endl
#define end(v) v.end()
#define bg(v) v.begin()
#define all(v) (v.begin(), v.end())
#define pb push_back


using namespace std;

mt19937 rng(1230);

vpi ZapisiTacke(int N){
    vpi tacke(N+1);
    tacke[1] = {0, 0};
    FOR(i, 2, N + 1)tacke[i] = {1, i - 2};
    //trav(el, tacke)cerr << el.f << ":" << el.s << " ";
    //cerr << nl;
    return tacke;
}

void podeli(int L, int R, vi &cur, vi &res, int r){
    //cerr << L << " " << R << endl;
    if(L == R){
        res[cur[0]] = L;
        return;
    }
    int piv = cur[rng() % sz(cur)];
    vi le, de;
    trav(el, cur){
        if(el == piv)continue;
        int x = Pitaj(r, piv, el);
        if(x == 1)le.pb(el);
        else de.pb(el);
    }
    //trav(el, le)cerr << el << " ";
    //cerr << nl;
    //trav(el, de)cerr << el << " ";
    //cerr << nl;
    res[piv] = L + sz(de);
    if(sz(de))podeli(L, L + sz(de) - 1, de, res, r);
    if(sz(le))podeli(L + sz(de) + 1, R, le, res, r);
}

vi Resi(int n, int Q){
    vi resenje(n+1);
    vi p;
    int r;
    while(true){
        int i = rng() % n + 1, j = rng() % n + 1, k = rng() % n + 1;
        while(j == i)j = rand() % n + 1;
        while(k == j || k == i)k = rng() % n + 1;
        int x = Pitaj(i, j, k);
        if(!x){
            p.pb(i);
            p.pb(j);
            p.pb(k);
            break;
        }
    }
    //trav(el, p)cerr << el << " ";
    //cerr << nl;
    FOR(i, 1, n + 1){
        if(i == p[0] || i == p[1] || i == p[2])continue;
        int x = Pitaj(p[0], p[1], i);
        if(!x)p.pb(i);
        else {
            r = i;
            FOR(j, i + 1, n + 1){
                if(j == p[0] || j == p[1] || j == p[2])continue;
                p.pb(j);
            }
            break;
        }
    }
    //cerr << r << endl;
    resenje[r] = 1;
    podeli(2, n, p, resenje, r);
    return resenje;
}

/*
10 1000
3 2 1 5 10 4 8 7 9 6

10 1000
10 9 8 7 3 2 1 6 5 4
*/