#include <bits/stdc++.h>
using namespace std;
#include "Anna.h"
namespace {
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}
const int MX = 3.9e6;
const int MN = 2000;
}
int Declare(){
return MN;
}
pair<vi, vi> Anna(ll input){
ll in1 = input & 511;
ll in2 = (input >> 9) & 511;
ll in3 = input >> 18;
/*dbg(in1);
dbg(in2);
dbg(in3);*/
vi s1, s2;
FR(i, 9) FR(j, 1<<i) s1.pb((in1 >> i) & 1);
FR(i, 9) FR(j, 1<<i) s2.pb((in2 >> i) & 1);
reverse(ALL(s2));
ll x = in3;
int len = 0, pop = -1;
while(len < MN){
int dif = len*2;
if(x < dif){
pop = x;
break;
}
x -= dif;
len++;
}
//dbg(len);
vi v1(len), v2(len);
FR(i, len) if(pop) v1[i] = 1, pop--;
FR(i, len) if(pop) v2[i] = 1, pop--;
vi res1 = vi(s1);
for(int a : v1) res1.pb(a);
for(int a : s2) res1.pb(a);
vi res2 = vi(s1);
for(int a : v2) res2.pb(a);
for(int a : s2) res2.pb(a);
//dbg(SZ(res1));
//dbg(SZ(res2));
return {res1, res2};
}
#include <bits/stdc++.h>
using namespace std;
#include "Bruno.h"
namespace {
typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}
const int MX = 3.9e6;
const int MN = 2000;
}
ll Bruno(vi u){
int n = SZ(u);
int pop = 0;
ll v1 = 0;
vi inds[2];
int offs[2] = {0, 0};
FR(i, n) inds[u[i]].pb(i);
inds[0].pb(INF); inds[1].pb(INF);
FR(i, 9){
int val = inds[1][offs[1]] < inds[0][offs[0]];
v1 |= val << i;
pop -= val * (2 << i);
offs[val] += 2 << i;
}
reverse(ALL(u));
ll v2 = 0;
inds[0].clear(), inds[1].clear();
offs[0] = offs[1] = 0;
FR(i, n) inds[u[i]].pb(i);
inds[0].pb(INF); inds[1].pb(INF);
FR(i, 9){
int val = inds[1][offs[1]] < inds[0][offs[0]];
v2 |= val << i;
pop -= val * (2 << i);
offs[val] += 2 << i;
}
reverse(ALL(u));
ll v3 = 0;
int fullLen = SZ(u) - 511*4;
int len = 0;
while(len < fullLen/2){
int dif = len*2;
v3 += dif;
len++;
}
for(int a : u) pop += a;
assert(pop >= 0);
v3 += pop;
/*dbg(v1);
dbg(v2);
dbg(v3);*/
return (v3 << 18) | (v2 << 9) | v1;
}
