#include "Ali.h"
#include <string>
#include <vector>
#include<cassert>
#include<iostream>
#define pb push_back
using namespace std;
namespace {
vector<int> dep, tab, gdzie;
vector<vector<int> > E;
int blo_siz=14;
int blo_num=1440;
int max_pot=14;
string enc(int a){
string res(max_pot, '0');
for(int i=0; i<max_pot; i++){
res[i]='0'+!!(a&(1<<i));
}
return res;
}
int dec(string s){
int res=0;
for(int i=0; i<s.size(); i++){
res+=(1<<i)*(s[i]-'0');
}
return res;
}
pair<int, int> dec2(int x){
//cerr<<x<<" ";
for(int i=0; i<blo_num; i++){
if(x<blo_num-i){
//cerr<<i<<" "<<x<<"\n";
return {i, i+x};
}
else x-=blo_num-i;
}
assert(false);
}
}
void dfs(int v, int p){
//cerr<<v<<" "<<p<<endl;
gdzie[v]=tab.size();
tab.pb(dep[v]);
for(int u:E[v]){
if(u!=p){
dep[u]=dep[v]+1;
dfs(u, v);
tab.pb(dep[v]);
}
}
}
void Init(int n, std::vector<int> U, std::vector<int> V) {
E.clear();
gdzie.clear();
dep.clear();
tab.clear();
gdzie.resize(n);
dep.resize(n);
E.resize(n);
for(int i=0; i<n-1; i++){
//cerr<<U[i]<<" "<<V[i]<<endl;
E[U[i]].pb(V[i]);
E[V[i]].pb(U[i]);
}
dfs(0, -1);
for(int i=0; i<n; i++){
SetID(i, gdzie[i]);
}
while(tab.size()%blo_siz){
tab.pb(tab.back()+1);
}
}
string SendA(std::string s) {
pair<int, int> x=dec2(dec(s));
int b1=x.first, b2=x.second;
int mini=(1<<max_pot)-1;
string res;
for(int i=b1+1; i<b2; i++){
for(int j=i*blo_siz; j<(i+1)*blo_siz; j++){
mini=min(mini, tab[j]);
}
}
res+=enc(mini);
res+=enc(tab[b1*blo_siz]);
for(int i=b1*blo_siz+1; i<blo_siz*(b1+1); i++){
res+='0'+char(tab[i]>tab[i-1]);
}
res+=enc(tab[b2*blo_siz]);
for(int i=b2*blo_siz+1; i<blo_siz*(b2+1); i++){
res+='0'+char(tab[i]>tab[i-1]);
}
return res;
}
#include "Benjamin.h"
#include <string>
#include <vector>
#include<cassert>
#include<iostream>
using namespace std;
namespace {
int blo_siz=14;
int blo_num=1440;
int max_pot=14;
int X, Y;
string enc(int a){
string res(20, '0');
for(int i=0; i<20; i++){
res[i]='0'+!!(a&(1<<i));
}
return res;
}
int dec(string s){
//cerr<<s<<"\n";
int res=0;
for(int i=0; i<s.size(); i++){
res+=(1<<i)*(s[i]-'0');
}
return res;
}
int enc2(int a, int b){
//cerr<<a<<" "<<b<<" ";
int r=0;
for(int i=0; i<a; i++){
r+=blo_num-i;
}
r+=b-a;
//cerr<<r<<"\n";
return r;
}
}
string SendB(int N, int _X, int _Y) {
X=_X;
Y=_Y;
if(X>Y)swap(X, Y);
return enc(enc2(X/blo_siz, Y/blo_siz));
}
int Answer(string s) {
int mini=dec(s.substr(0, max_pot));
vector<int> blo1(blo_siz), blo2(blo_siz);
blo1[0]=dec(s.substr(max_pot, max_pot));
for(int i=1; i<blo_siz;i++){
if(s[max_pot*2-1+i]=='1')blo1[i]=blo1[i-1]+1;
else blo1[i]=blo1[i-1]-1;
}
blo2[0]=dec(s.substr(2*max_pot+blo_siz-1, max_pot));
for(int i=1; i<blo_siz;i++){
if(s[max_pot*3+blo_siz-2+i]=='1')blo2[i]=blo2[i-1]+1;
else blo2[i]=blo2[i-1]-1;
}
int ans=blo1[X%blo_siz]+blo2[Y%blo_siz];
if(X/blo_siz!=Y/blo_siz){
for(int i=X%blo_siz;i<blo_siz; i++){
mini=min(mini, blo1[i]);
}
for(int i=Y%blo_siz;i>=0; i--){
mini=min(mini, blo2[i]);
}
}
else{
for(int i=X%blo_siz;i<=Y%blo_siz; i++){
mini=min(mini, blo1[i]);
}
}
return ans-2*mini;
}
