#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "doll.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//namespace {
//
//constexpr int P_MAX = 20000000;
//constexpr int S_MAX = 400000;
//
//int M, N;
//std::vector<int> A;
//
//bool answered;
//int S;
//std::vector<int> IC, IX, IY;
//
//int read_int() {
// int x;
// if (scanf("%d", &x) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// return x;
//}
//
//void wrong_answer(const char *MSG) {
// printf("Wrong Answer: %s\n", MSG);
// exit(0);
//}
//
//void simulate() {
// if (S > S_MAX) {
// char str[50];
// sprintf(str, "over %d switches", S_MAX);
// wrong_answer(str);
// }
// for (int i = 0; i <= M; ++i) {
// if (!(-S <= IC[i] && IC[i] <= M)) {
// wrong_answer("wrong serial number");
// }
// }
// for (int j = 1; j <= S; ++j) {
// if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
// wrong_answer("wrong serial number");
// }
// if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
// wrong_answer("wrong serial number");
// }
// }
//
// int P = 0;
// std::vector<bool> state(S + 1, false);
// int pos = IC[0];
// int k = 0;
// FILE *file_log = fopen("log.txt", "w");
// fprintf(file_log, "0\n");
// for (;;) {
// fprintf(file_log, "%d\n", pos);
//// cout << pos << ' ';
// if (pos < 0) {
// if (++P > P_MAX) {
// fclose(file_log);
// char str[50];
// sprintf(str, "over %d inversions", P_MAX);
// wrong_answer(str);
// }
// state[-pos] = !state[-pos];
// pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
// } else {
// if (pos == 0) {
// break;
// }
// if (k >= N) {
// fclose(file_log);
// wrong_answer("wrong motion");
// }
// if (pos != A[k++]) {
// fclose(file_log);
// wrong_answer("wrong motion");
// }
// pos = IC[pos];
// }
// }
// fclose(file_log);
// if (k != N) {
// wrong_answer("wrong motion");
// }
// for (int j = 1; j <= S; ++j) {
// if (state[j]) {
// wrong_answer("state 'Y'");
// }
// }
// printf("Accepted: %d %d\n", S, P);
//}
//
//} // namespace
//
//void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
// if (answered) {
// wrong_answer("answered not exactly once");
// }
// answered = true;
// // check if input format is correct
// if ((int)C.size() != M + 1) {
// wrong_answer("wrong array length");
// }
// if (X.size() != Y.size()) {
// wrong_answer("wrong array length");
// }
// S = X.size();
// IC = C;
// IX = X;
// IY = Y;
//}
const int Nm = 4e5 + 10;
int cnt;
int x[Nm], y[Nm];
int build(int L, int R, int k, int n) {
if (L == R) return 1e9; // leaf
int cur = ++cnt;
int mid = L + R >> 1;
if (n >> k & 1) {
x[cur] = build(L, mid, k - 1, n);
y[cur] = build(mid + 1, R, k - 1, (1 << k) - 1);
} else {
x[cur] = 1;
y[cur] = build(L, mid, k - 1, n);
}
return cur;
}
int Flip[Nm];
void add(int u, int val) {
assert(u >= 0);
Flip[u] ^= 1;
if (Flip[u]) {
if (x[u] == 1e9) {
x[u] = - val;
return;
}
add(x[u], val);
} else {
if (y[u] == 1e9) {
y[u] = - val;
return;
}
add(y[u], val);
}
}
void create_circuit(int M, std::vector<int> A) {
vector<int> C(M + 1);
A.push_back(0);
int N = A.size();
int m = 0;
while ((1 << m) < N) ++m;
build(0, (1 << m) - 1, m - 1, N - 1);
// build(N);
// cout << cnt << '\n';
//assert(0);
for (int i = 0; i < N; ++i) add(1, A[i]);
// for (int i = 1; i <= cnt; ++i) cout << x[i] << ' ' << y[i] << '\n';
// exit(0);
for (int i = 0; i <= M; ++i) C[i] = -1;
vector <int> X, Y;
for (int i = 1; i <= cnt; ++i) X.push_back(- x[i]), Y.push_back(- y[i]);
// cout << X.size() << ' ' << Y.size() << '\n';
answer(C, X, Y);
}
//
//int main() {
//// freopen("test.inp", "r", stdin);
// M = read_int();
// N = read_int();
// A.resize(N);
// for (int k = 0; k < N; ++k) {
// A[k] = read_int();
// }
//
// answered = false;
// create_circuit(M, A);
// if (!answered) {
// wrong_answer("answered not exactly once");
// }
// FILE *file_out = fopen("out.txt", "w");
// fprintf(file_out, "%d\n", S);
// for (int i = 0; i <= M; ++i) {
// fprintf(file_out, "%d\n", IC[i]);
// }
// for (int j = 1; j <= S; ++j) {
// fprintf(file_out, "%d %d\n", IX[j - 1], IY[j - 1]);
// }
// fclose(file_out);
// simulate();
// return 0;
//}
