#include "code.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
template<typename T1,typename T2>void chmn(T1 &x,const T2 &y){x=x<y?x:y;}
template<typename T1,typename T2>void chmx(T1 &x,const T2 &y){x=x>y?x:y;}
mt19937 rng(time(0));
vector<pair<int,int>> ZapisiTacke(int n){
    vector<pair<int,int>>tacke(n+1);
    int m=n/2+1;
    for(int i=1;i<=m;i++)tacke[i]={i,0};
    for(int i=m+1;i<=n;i++)tacke[i]={i,1};
    //for(auto [x,y]:tacke)printf("[%i %i] ",x,y);printf("\n");
    return tacke;
}
vector<int> Resi(int n, int Q){
    vector<int>a,b;
    int was[n+10]={0};
    while(1){
        int i=rng()%n+1,j=rng()%n+1;
        while(j==i)j=rng()%n+1;
        int k=rng()%n+1;
        while(k==i||k==j)k=rng()%n+1;
        if(Pitaj(i,j,k)==0){
            a={i,j,k};
            was[i]=was[j]=was[k]=1;
            break;
        }
    }
    for(int i=1;i<=n;i++)if(!was[i]){
        if(Pitaj(a[0],a[1],i)==0)a.pb(i),was[i]=1;
        else b.pb(i),was[i]=2;
    }
    if(a.size()<b.size())swap(a,b);
    shuffle(a.begin(),a.end(),rng);
    shuffle(b.begin(),b.end(),rng);
    //for(int i=1;i<=n;i++)printf("%i ",was[i]);printf("\n");
    sort(a.begin(),a.end(),[&](int i,int j){
         if(Pitaj(b[0],i,j)==1)return true;
         return false;
    });
    sort(b.begin(),b.end(),[&](int i,int j){
         if(Pitaj(a[0],i,j)==-1)return true;
         return false;
    });
    //for(auto i:a)printf("%i ",i);printf("\n");
    //for(auto i:b)printf("%i ",i);printf("\n");
    vector<int>res(n+1);
    int ct=0;
    for(auto i:a)res[i]=++ct;
    for(auto i:b)res[i]=++ct;
    vector<int>ans(n+1);
    for(int i=1;i<=n;i++)ans[res[i]]=i;
    //for(int i=1;i<=n;i++)printf("%i ",ans[i]);printf("\n");
    return res;
}