// Bolatulu
#include <bits/stdc++.h>
#include "communication.h"
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define pb push_back
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,md
#define TR v+v+1,md+1,tr
#define Tl t[v].l,tl,md
#define Tr t[v].r,md+1,tr
#define all(x) (x).begin(),(x).end()
#define yes cout << "YES\n"
#define no cout << "NO\n"
// #define int long long
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define ld long double
using namespace std;
int binpow(int a,int n,int M) {
if (n==0)
return 1;
if (n%2!=0)
return (a * binpow(a,n-1,M))%M;
int z=binpow(a,n/2,M);
return (z*z)%M;
}
const ll INF = 1e18+7;
const int N = 1e5+7;
const int M = 1e4+7;
const ld eps = 1e-3;
pair <int,int> calc(int a,int b,int c,int d) {
if (b==c) {
if (b)
return {1,3};
return {2,-1};
}
if (a==d) {
if (a)
return {1,3};
return {1,-1};
}
if (a==b)
return {3,-1};
return {1,-1};
}
void encode(int n,int x) {
int m=n;
deque <pair <int,int>> v={{1,n}};
while (m>2) {
deque <pair <int,int>> v1,v2,v3;
int m1=m/3,m2=m/3,m3=m/3;
if (m%3>0)
m3++;
if (m%3>1)
m2++;
while (!v.empty() and v[0].S-v[0].F+1<=m1) {
m1-=v[0].S-v[0].F+1;
v1.pb(v[0]);
v.pop_front();
}
if (m1>0) {
int l=v[0].F,r=v[0].S;
v1.eb(l,l+m1-1);
v.pop_front();
v.push_front({l+m1,r});
m1=0;
}
while (!v.empty() and v[0].S-v[0].F+1<=m2) {
m2-=v[0].S-v[0].F+1;
v2.pb(v[0]);
v.pop_front();
}
if (m2>0) {
int l=v[0].F,r=v[0].S;
v2.eb(l,l+m2-1);
v.pop_front();
v.push_front({l+m2,r});
m2=0;
}
while (!v.empty() and v[0].S-v[0].F+1<=m3) {
m3-=v[0].S-v[0].F+1;
v3.pb(v[0]);
v.pop_front();
}
bool ok1=false,ok2=false;
for (auto now : v1) {
if (x>=now.F and x<=now.S)
ok1=true;
}
for (auto now : v2) {
if (x>=now.F and x<=now.S)
ok2=true;
}
pair <int,int> z=calc(send(ok1),send(ok2),send(ok2),send(ok1));
m1=m/3,m2=m/3,m3=m/3;
if (m%3>0)
m3++;
if (m%3>1)
m2++;
if (z.F==1) {
m-=m1;
v1.clear();
} else if (z.F==2) {
m-=m2;
v2.clear();
} else {
m-=m3;
v3.clear();
}
if (z.S==1) {
m-=m1;
v1.clear();
} else if (z.S==2) {
m-=m2;
v2.clear();
} else if (z.S==3) {
m-=m3;
v3.clear();
}
v=v1;
v.ins(v.end(),all(v2));
v.ins(v.end(),all(v3));
}
}
pair <int,int> decode(int n) {
int m=n;
deque <pair <int,int>> v={{1,n}};
while (m>2) {
deque <pair <int,int>> v1,v2,v3;
int m1=m/3,m2=m/3,m3=m/3;
if (m%3>0)
m3++;
if (m%3>1)
m2++;
while (!v.empty() and v[0].S-v[0].F+1<=m1) {
m1-=v[0].S-v[0].F+1;
v1.pb(v[0]);
v.pop_front();
}
if (m1>0) {
int l=v[0].F,r=v[0].S;
v1.eb(l,l+m1-1);
v.pop_front();
v.push_front({l+m1,r});
m1=0;
}
while (!v.empty() and v[0].S-v[0].F+1<=m2) {
m2-=v[0].S-v[0].F+1;
v2.pb(v[0]);
v.pop_front();
}
if (m2>0) {
int l=v[0].F,r=v[0].S;
v2.eb(l,l+m2-1);
v.pop_front();
v.push_front({l+m2,r});
m2=0;
}
while (!v.empty() and v[0].S-v[0].F+1<=m3) {
m3-=v[0].S-v[0].F+1;
v3.pb(v[0]);
v.pop_front();
}
pair <int,int> z=calc(receive(),receive(),receive(),receive());
m1=m/3,m2=m/3,m3=m/3;
if (m%3>0)
m3++;
if (m%3>1)
m2++;
if (z.F==1) {
m-=m1;
v1.clear();
} else if (z.F==2) {
m-=m2;
v2.clear();
} else {
m-=m3;
v3.clear();
}
if (z.S==1) {
m-=m1;
v1.clear();
} else if (z.S==2) {
m-=m2;
v2.clear();
} else if (z.S==3) {
m-=m3;
v3.clear();
}
v=v1;
v.ins(v.end(),all(v2));
v.ins(v.end(),all(v3));
}
return {v[0].F,v[1].F};
}
/*
signed main() {
// file("jenga");
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int test = 1;
solve(3);
// cin >> test;
while (test--) {
// solve();
if (test)
cout << '\n';
}
return 0;
}
*/
