#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
const int INF = 1e9;
void create_circuit(int m, vi a) {
int n = a.size();
a.pb(0);
vi C(m + 1);
C[0] = a[0];
for (int i = 1; i <= m; ++i) {
C[i] = 0;
}
vector<vi> tmp(m+1);
FOR(i, 0, n-1) {
tmp[a[i]].pb(a[i+1]);
}
vector<vi> out;
vi pr;
vi X, Y;
//cout << " hh" << endl;
FOR(i, 1, m) {
// cout << " i = " << i << endl;
vi cur;
cur.pb(i);
// cout << " asdaasdasd s " << endl;
for (int xx : tmp[i]) {
// cout << " pushing xx = " << xx << endl;
cur.pb(xx);
// cout << " after pu" << endl;
}
// cout <<" asdffsfsdfsdfsdfds" << endl;
out.pb(cur);
}
//cout << " asdas" << endl;
FOR(i, 0, (int)out.size()-1) {
// cout << " i=" << i << endl;
vi cur = out[i];
out[i].clear();
cout << " cur: ";
for (int xx : cur) cout << xx << " ";
cout << endl;
int id = cur[0];
if ((int)cur.size() == 1) {
if (id > 0) C[id] = 0;
else if (id < 0) X[abs(id)] = id, Y[abs(id)] = 0;
continue;
}
if ((int)cur.size() == 2) {
int to = cur[1];
if (id > 0) C[id] = to;
else if (id < 0) X[abs(id)] = id, Y[abs(id)] = to;
continue;
}
if (id > 0) {
vi nw;
int scnt = (int)X.size();
scnt++;
X.pb(0); Y.pb(0); pr.pb(id);
nw.pb(-scnt);
C[id] = -scnt;
FOR(j, 1, (int)cur.size()-1) nw.pb(cur[j]);
out.pb(nw);
continue;
}
vi one, two;
//int scnt = (int)X.size();
//scnt++;
//REP(2) {X.pb(0); Y.pb(0);}
bool b = false;
//X[id] = -scnt;
//Y[id] =
//one.pb(-scnt);
//two.pb(-(scnt+1));
int twoPwr = 1;
while (twoPwr < (int)cur.size()-1) {
twoPwr *= 2;
}
REP(twoPwr - (int)cur.size()+1) {
if (!b)
one.pb(INF);
else
two.pb(INF);
b = !b;
}
FOR(j, 1, (int)cur.size()-1) {
if (!b)
one.pb(cur[j]);
else
two.pb(cur[j]);
b = !b;
}
if ((int)one.size() == 1) X[abs(id)-1] = one[0];
else {
int scnt = (int)X.size();
scnt++;
X.pb(0); Y.pb(0); pr.pb(id);
X[abs(id)-1] = -scnt;
reverse(one.begin(), one.end());
one.pb(-scnt);
reverse(one.begin(), one.end());
out.pb(one);
}
if ((int)two.size() == 1) Y[abs(id)-1] = two[0];
else {
int scnt = (int)X.size();
scnt++;
X.pb(0); Y.pb(0); pr.pb(id);
Y[abs(id)-1] = -scnt;
reverse(two.begin(), two.end());
two.pb(-scnt);
reverse(two.begin(), two.end());
out.pb(two);
}
//out.pb(one);
//out.pb(two);
}
FOR(i, 0, (int)X.size()-1) {
if (X[i] == INF) X[i] = pr[i];
if (Y[i] == INF) Y[i] = pr[i];
}
answer(C, X, Y);
}
/*
4 4
1 2 1 3
*/
