#include"communication.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
vector<int> message[4] =
{{0,0,0,0},
{0,1,1,0},
{1,0,0,1},
{1,1,1,1}};
vector<int> contrast(vector<int> R){
vector<int> ret;
forf(x,0,3){
int f = 1;
forf(i,0,2) if(R[i]!=message[x][i] && R[i+1]!=message[x][i+1]) f = 0;
if(f) ret.pb(x);
}
return ret;
}
vector<int> fib[31];
void fibdfs(int n, int now, int i){
if(i == -1){ fib[n].pb(now); return;}
fibdfs(n,now,i-1);
if(!(now&(1<<(i+1)))) fibdfs(n,now^(1<<i),i-1);
}
void getfib(int n){
if(sz(fib[n])) return;
fibdfs(n,0,n-1);
}
int piv = 1e9+1;
vector<int> enc(int N, int X){
if(N==2) return {0,1};
if(N==1) return {0};
if(N>=piv) {
int n = 1;
while ((1 << n) < N) n++;
getfib(n);
int R = 0;
forf(i, 0, n - 1) R += send((X & (1 << i)) ? 1 : 0) * (1 << i);
int nx = idx(X ^ R, fib[n]);
auto v = enc(sz(fib[n]), nx);
vector<int> ret;
for (int i: v) if(i < sz(fib[n])) ret.pb(R ^ fib[n][i]);
return ret;
}
else{
int p[5];
forf(i,0,4) p[i] = (double)N / 4 * i;
int I;
forf(i,0,4) if(X>=p[i]) I = i;
vector<int> R;
forf(i,0,3) R.pb(send(message[I][i]));
vector<pair<int,int> > intv;
int nN=0,nX=0;
for(auto i : contrast(R)) intv.pb({p[i],p[i+1]}), nN += p[i+1]-p[i];
if(X < intv[0].se) nX = X-intv[0].fs;
else nX = intv[0].se-intv[0].fs + X-intv[1].fs;
vector<int> res = enc(nN,nX);
vector<int> ret;
for(auto i : res){
if(i < intv[0].se-intv[0].fs) ret.pb(intv[0].fs+i);
else ret.pb(intv[1].fs+ i-(intv[0].se-intv[0].fs));
}
return ret;
}
}
vector<int> dec(int N){
if(N==2) return {0,1};
if(N==1) return {0};
if(N>=piv) {
int n = 1;
while ((1 << n) < N) n++;
getfib(n);
int R = 0;
forf(i, 0, n - 1) R += receive() * (1 << i);
auto v = dec(sz(fib[n]));
vector<int> ret;
for (int i : v) if(i < sz(fib[n])) ret.pb(R ^ fib[n][i]);
return ret;
}
else{
int p[5];
forf(i,0,4) p[i] = (double)N / 4 * i;
vector<int> R;
forf(i,0,3) R.pb(receive());
vector<pair<int,int> > intv;
int nN=0;
for(auto i : contrast(R)) intv.pb({p[i],p[i+1]}), nN += p[i+1]-p[i];
vector<int> res = dec(nN);
vector<int> ret;
for(auto i : res){
if(i < intv[0].se-intv[0].fs) ret.pb(intv[0].fs+i);
else ret.pb(intv[1].fs+ i-(intv[0].se-intv[0].fs));
}
return ret;
}
}
void encode(int N, int X) {
auto trash = enc(N,X-1);
}
std::pair<int, int> decode(int N) {
vector<int> ans = dec(N);
if(sz(ans)== 1) return {ans[0]+1,ans[0]+1};
else return {ans[0]+1, ans[1]+1};
}
