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

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

int partition(int tl, int tr) {
	int pivot = tl + (int)(rand() % (tr - tl + 1));
	swap(res[tl], res[pivot]);
	pivot = tl++;
	while(tl <= tr) {
		if(Pitaj(res[1], res[pivot], res[tl]) < 0)
			tl++;
		else {
			swap(res[tl], res[tr]);
			tr--;
		}
	}
	swap(res[pivot], res[tr]);
	return tr;
}

// geometrijski pivot = 1
void quick(int l, int r) {
	if(l > r || l == r)
		return;
	int m = partition(l, r);
	quick(l, m-1);
	quick(m+1, r);
}

int nadji_pivota() {
	for(int i = 1; i <= N-2; i += 3) {
		if(Pitaj(i, i+1, i+2) == 0)
			continue;
		int spored;
		if(i > 1)
			spored = 1;
		else
			spored = 4;
		if(Pitaj(i, i+1, spored) == 0)
			return i+2;
		if(Pitaj(i, i+2, spored) == 0)
			return i+1;
		return i;
	}
	if(N % 3 == 1)
		return N;
	if(Pitaj(1, 2, N) == 0)
		return N-1;
	return N;
}

vector<int> Resi(int n, int q) {
	srand(time(0));
	res.resize(n+1);
	for(int i = 1; i <= n; i++) {
		res[i] = i;
	}
	int pivot = nadji_pivota();
	swap(res[1], res[pivot]);
	quick(2, n);
	vector<int> rezultat(n+1);
	for(int i = 1; i <= n; i++) {
		rezultat[res[i]] = i;
	}
	return rezultat;
}