#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
const int PAIU=100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) {
return a+rng()%(b-a+1);
}
#define forn(i,n) for (int i=0; i<n; ++i)
pair<int,int> decode(int n) {
int len=4;
vector<vector<vector<vector<int>>>> dp((1<<len),vector<vector<vector<int>>>(len,vector<vector<int>>(2)));
for (int x=0; x<(1<<len); ++x) {
dp[x][0][0].push_back(x&1);
dp[x][0][1].push_back(!(x&1));
for (int l=1; l<len; ++l) {
for (auto v:dp[x][l-1][0]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
dp[x][l][1].push_back(v+((!((x>>l)&1))<<l));
}
for (auto v:dp[x][l-1][1]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
}
}
}
vector<int> a; forn(i,n) a.push_back(i+1);
while (a.size()>2) {
//cout<<"iter\n";
//for (auto x:a) cout<<x<<' '; cout<<'\n';
int n=a.size();
int f = n/3 + !!(n%3);
int s = 2*(n/3) + ((n%3) == 2);
int y=0;
for (int i=0; i<4; ++i) {
y<<=1; y+=receive();
}
vector<int> b;
vector<int> match;
for (auto v:dp[0][len-1][0]) if (v==y) {
for (int i=0; i<f; ++i) b.push_back(a[i]);
}
for (auto v:dp[0][len-1][1]) if (v==y) {
for (int i=0; i<f; ++i) b.push_back(a[i]);
}
for (auto v:dp[6][len-1][0]) if (v==y) {
for (int i=f; i<s; ++i) b.push_back(a[i]);
}
for (auto v:dp[6][len-1][1]) if (v==y) {
for (int i=f; i<s; ++i) b.push_back(a[i]);
}
for (auto v:dp[9][len-1][0]) if (v==y) {
for (int i=s; i<n; ++i) b.push_back(a[i]);
}
for (auto v:dp[9][len-1][1]) if (v==y) {
for (int i=s; i<n; ++i) b.push_back(a[i]);
}
a=b;
}
if (a.size()==1) a.push_back(a[0]);
return {a[0],a[1]};
}
void encode(int n, int x) {
int len=4;
vector<vector<vector<vector<int>>>> dp((1<<len),vector<vector<vector<int>>>(len,vector<vector<int>>(2)));
for (int x=0; x<(1<<len); ++x) {
dp[x][0][0].push_back(x&1);
dp[x][0][1].push_back(!(x&1));
for (int l=1; l<len; ++l) {
for (auto v:dp[x][l-1][0]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
dp[x][l][1].push_back(v+((!((x>>l)&1))<<l));
}
for (auto v:dp[x][l-1][1]) {
dp[x][l][0].push_back(v+(x&(1<<l)));
}
}
//if (x==0 || x==6 || x==9 || x==15) {
//cout<<x<<": ";
//for (auto p:dp[x][len-1][0]) cout<<p<<' ';
//for (auto p:dp[x][len-1][1]) cout<<p<<' ';
//cout<<'\n';
//}
}
vector<int> a; forn(i,n) a.push_back(i+1);
while (a.size()>2) {
//cout<<"iter\n";
//for (auto x:a) cout<<x<<' '; cout<<'\n';
int n=a.size();
int f = n/3 + !!(n%3);
int s = 2*(n/3) + ((n%3) == 2);
int l=0, r=n-1;
while (l<r) {
int mid=(l+r+1)>>1;
if (a[mid]>x) r=mid-1;
else l=mid;
}
int y=0;
if (r<f) {
y<<=1; y+=send(0);
y<<=1; y+=send(0);
y<<=1; y+=send(0);
y<<=1; y+=send(0);
} else if (r<s) {
y<<=1; y+=send(0);
y<<=1; y+=send(1);
y<<=1; y+=send(1);
y<<=1; y+=send(0);
} else {
y<<=1; y+=send(1);
y<<=1; y+=send(0);
y<<=1; y+=send(0);
y<<=1; y+=send(1);
}
vector<int> b;
vector<int> match;
for (auto v:dp[0][len-1][0]) if (v==y) {
for (int i=0; i<f; ++i) b.push_back(a[i]);
}
for (auto v:dp[0][len-1][1]) if (v==y) {
for (int i=0; i<f; ++i) b.push_back(a[i]);
}
for (auto v:dp[6][len-1][0]) if (v==y) {
for (int i=f; i<s; ++i) b.push_back(a[i]);
}
for (auto v:dp[6][len-1][1]) if (v==y) {
for (int i=f; i<s; ++i) b.push_back(a[i]);
}
for (auto v:dp[9][len-1][0]) if (v==y) {
for (int i=s; i<n; ++i) b.push_back(a[i]);
}
for (auto v:dp[9][len-1][1]) if (v==y) {
for (int i=s; i<n; ++i) b.push_back(a[i]);
}
a=b;
}
return;
for (int i=0; i<(1<<len); ++i) {
for (int j=i+1; j<(1<<len); ++j) {
for (int k=j+1; k<(1<<len); ++k) {
for (int l=k+1; l<(1<<len); ++l) {
int paiu=0;
for (auto x:dp[i][len-1][0]) {
for (auto y:dp[j][len-1][0]) {
for (auto z:dp[k][len-1][0]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
for (auto z:dp[k][len-1][1]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
}
for (auto y:dp[j][len-1][1]) {
for (auto z:dp[k][len-1][0]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
for (auto z:dp[k][len-1][1]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
}
}
for (auto x:dp[i][len-1][1]) {
for (auto y:dp[j][len-1][0]) {
for (auto z:dp[k][len-1][0]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
for (auto z:dp[k][len-1][1]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
}
for (auto y:dp[j][len-1][1]) {
for (auto z:dp[k][len-1][0]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
for (auto z:dp[k][len-1][1]) {
for (auto q:dp[l][len-1][0]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
for (auto q:dp[l][len-1][1]) {
paiu|=(x==y && y==z);
paiu|=(x==y && y==q);
paiu|=(x==z && z==q);
paiu|=(y==z && z==q);
}
}
}
}
if (paiu==0) {
cout<<"! "<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
}
}
}
}
}
}
