//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
#include "popa.h"
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;
const ll DIM = 700007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 998244353;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };
FILE* stream;
set < pair < pair < pii, pii >, bool > > Q;
bool queryx(int a, int b, int c, int d) {
pair < pair < pii, pii >, bool > v1 = { {{a, b}, {c, d}}, 0 };
pair < pair < pii, pii >, bool > v2 = { {{a, b}, {c, d}}, 1 };
if (!Q.count(v1) && !Q.count(v2)) {
bool ans = query(a, b, c, d);
if (ans == 0) Q.insert(v1);
else Q.insert(v2);
}
if (Q.count(v1)) return 0;
if (Q.count(v2)) return 1;
}
ll findGCD(ll L, ll R, bool prev) {
if (L == R) return L;
ll mid = (L + R) / 2;
if (!prev) {
if (queryx(L, mid, L, R)) return findGCD(L, mid, true);
else return findGCD(mid + 1, R, false);
}
else {
if (queryx(mid + 1, R, L, R)) return findGCD(mid + 1, R, false);
else return findGCD(L, mid, true);
}
}
bool pr = false;
ll buildSubTree(ll L, ll R, int* Left, int* Right) {
if (L == R) {
Left[L] = -1;
Right[L] = -1;
return L;
}
if (L > R) return -1;
ll root = findGCD(L, R, pr);
pr ^= 1;
Left[root] = buildSubTree(L, root - 1, Left, Right);
Right[root] = buildSubTree(root + 1, R, Left, Right);
return root;
}
int solve(int N, int* Left, int* Right) {
Q.clear();
return buildSubTree(0, N - 1, Left, Right);
}
/*
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen_s(&stream, "input.txt", "r", stdin);
//freopen_s(&stream, "output.txt", "w", stdout);
return 0;
}
*/
