#include "cmp.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int l, r, offset;
} t[20]{};
int substr(int n, int l, int r) {
n &= (1<<r) - 1;
n >>= l;
return n;
}
// 875 = 0011 0110 1011
void remember(int n)
{
t[1].l = 4;
t[1].r = 12;
t[2].l = 8;
t[2].r = 12;
t[3].l = 0;
t[3].r = 4;
t[4].l = 10;
t[4].r = 12;
t[5].l = 6;
t[5].r = 8;
t[6].l = 2;
t[6].r = 4;
int s = 1;
for (int idx : {1, 2, 3, 4, 5, 6}) {
auto &[l,r,o] = t[idx];
o = s;
bit_set(o + substr(n, l, r));
s += 1<<(t[idx].r-t[idx].l);
}
}
int compare(int b)
{
int idx = 1;
while (true)
{
if (idx == 4 || idx == 5 || idx == 6) break;
auto [l,r,o] = t[idx];
if (!bit_get(o + substr(b, l, r))) {
idx = 2 * idx;
}
else {
if (idx == 3) {
return 0;
}
idx = 2 * idx + 1;
}
}
if (idx == 4 || idx == 5 || idx == 6) {
int jdx = idx/2;
if (idx == 5) jdx = 1;
if (bit_get(t[idx].offset + substr(b, t[idx].l, t[idx].r))) {
int x = b>>t[jdx].l&1;
int y = b>>(t[jdx].l+1)&1;
if (x==y) {
if (x) return +1;
return -1;
}
else {
if (x) { // 01
if (bit_get(t[jdx].offset + (substr(b,t[jdx].l,t[jdx].r) &~3))) return +1;
return -1;
}
else { // 10
if (bit_get(t[jdx].offset + (substr(b,t[jdx].l,t[jdx].r) | 3) )) return -1;
return +1;
}
}
}
}
int x = b>>t[idx].l&1;
int y = b>>(t[idx].l+1)&1;
// b<a:-1
if (x==y) {
if (x) return +1;
return -1;
}
else {
if (x) { // 01 <-- 얘 있는 경우 --> 00이 존재한다면 b가 크다는 뜻
if (bit_get(t[idx].offset)) return +1;
return -1;
}
else { // 10 <-- 얘 있는 경우 --> 11이 존재한다면 b가 작다는 뜻
if (bit_get(t[idx].offset + 3)) return -1;
return +1;
}
}
}
