#include <bits/stdc++.h>
#include "library.h"
using namespace std;
vector<vector<int> > adj;
int n;
void recur(vector<int> options, int num) {
if ((int)options.size() == 1) {
vector<int> m;
m.resize(n, 0);
m[options[0]] = 1;
m[num] = 1;
if (Query(m) != 1) return;
adj[num].push_back(options[0]);
adj[options[0]].push_back(num);
return;
}
vector<int> cur;
for (int i = 0; i < options.size()/2; i++) {
cur.push_back(options[i]);
}
vector<int> m;
m.resize(n, 0);
for (int i = 0; i < cur.size(); i++) m[cur[i]] = 1;
int q1 = Query(m);
m[num] = 1;
int q2 = Query(m);
if (q1 == q2) recur(cur, num);
else {
cur.clear();
for (int i = options.size()/2; i < options.size(); i++) {
cur.push_back(options[i]);
}
recur(cur, num);
}
}
void recur1(vector<int> options, int num) {
if ((int)options.size() == 1) {
vector<int> m;
m.resize(n, 0);
m[options[0]] = 1;
m[num] = 1;
if (Query(m) != 1) return;
adj[num].push_back(options[0]);
adj[options[0]].push_back(num);
return;
}
vector<int> cur;
for (int i = 0; i < options.size()/2; i++) {
cur.push_back(options[i]);
}
vector<int> m;
m.resize(n, 0);
for (int i = 0; i < cur.size(); i++) m[cur[i]] = 1;
int q1 = Query(m);
m[num] = 1;
int q2 = Query(m);
vector<int> temp;// = cur;
for (int i = 0; i < cur.size(); i++) temp.push_back(cur[i]);
cur.clear();
for (int i = options.size()/2; i < options.size(); i++) {
cur.push_back(options[i]);
}
m.clear(); m.resize(n, 0);
for (int i = 0; i < cur.size(); i++) m[cur[i]] = 1;
int q3 = Query(m);
m[num] = 1;
int q4 = Query(m);
//printf("%d %d %d %d\n", q1, q2, q3, q4);
if (q1 == q2 && q3 == q4) {
recur(cur, num);
recur(temp, num);
}
else if (q1 == q2) recur(temp, num);
else if (q3 == q4) recur(cur, num);
else if (q2 < q1) recur1(temp, num);
else if (q4 < q3) recur1(cur, num);
else assert(false);
}
void Solve(int N) {
srand(492);
n = N;
if (n == 1) {
vector<int> res;
res.resize(1, 1);
Answer(res);
return;
}
adj.resize(n);
vector<int> options;
vector<int> cur;
deque<int> ans;
vector<bool> vis;
vis.resize(n, false);
int num = rand()%n;
int orig = num;
vis[num] = true;
for (int i = 0; i < n; i++) {
if (!vis[i]) options.push_back(i);
}
recur1(options, num);
//printf("%d\n", adj[num].size());
ans.push_back(num);
for (int i = 0; i < adj[orig].size(); i++) {
num = orig;
int prev = num;
num = adj[num][i];
if (i == 0) ans.push_back(num);
else ans.push_front(num);
vis[num] = true;
options.clear();
for (int j = 0; j < n; j++) if (!vis[j]) options.push_back(j);
if (options.size() == 0) break;
recur(options, num);
//printf("%d %d\n", num, adj[num].size());
while (adj[num].size() == 2) {
int newprev = num;
if (adj[num][0] == prev) num = adj[num][1];
else num = adj[num][0];
if (i == 0) ans.push_back(num);
else ans.push_front(num);
prev = newprev;
vis[num] = true;
options.clear();
for (int j = 0; j < n; j++) if (!vis[j]) options.push_back(j);
if (options.size() == 0) break;
recur(options, num);
//printf("%d %d\n", num, adj[num].size());
}
}
vector<int> res;
while (!ans.empty()) {
res.push_back(ans.front()+1);
ans.pop_front();
}
Answer(res);
return;
}
