#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
vector<vector<int>> adj;
string toBin(int n, int l) {
string s(l, '0');
for(int i=0;i<l;i++)
s[i] = !!(n & (1 << i)) + '0';
return s;
}
int toDec(string s) {
reverse(s.begin(),s.end());
int ans = 0;
for(auto i: s)
ans = (ans << 1) | (i & 1);
return ans;
}
int euler[20'005], dist[10'005], n;
}
void Init(int N, std::vector<int> U, std::vector<int> V) {
n = N;
adj.clear();
adj.resize(N);
for(int i=0;i<N-1;i++) {
adj[U[i]].push_back(V[i]);
adj[V[i]].push_back(U[i]);
}
auto dfs = [&adj,cnt=0](auto &self, int x, int p) mutable -> void {
SetID(x, cnt);
euler[cnt++] = x;
for(auto i: adj[x])
if(i != p) {
self(self, i, x);
euler[cnt++] = x;
}
};
dfs(dfs, 0, -1);
}
std::string SendA(std::string S) {
int M = toDec(S);
int x = M / 100 * 2;
int k = (M % 100) * 200;
auto dfs = [&adj](auto &self, int x, int p) mutable -> void {
for(auto i: adj[x])
if(i != p) {
dist[i] = dist[x] + 1;
self(self, i, x);
}
};
dist[euler[x+1]] = 0;
dfs(dfs, euler[x+1], -1);
int dst = dist[euler[k]];
dist[euler[x]] = 0;
dfs(dfs, euler[x], -1);
string ret;
for(int i=0;i<2*n-2;i++)
if(euler[i] == euler[x+1] && euler[i+1] == euler[x]) {
if(i >= k && i < k + 200)
ret = toBin(i - k, 8);
else
ret = toBin(-1, 8);
}
assert(ret.size() == 8);
ret += toBin(dist[euler[k]], 14);
if(dist[euler[k]] < dst)
ret += '1';
else
ret += '0';
for(int i=0;i<min(199,2*n-2-k);i++)
ret += (dist[euler[k+i+1]]>dist[euler[k+i]]?'1':'0');
return ret;
}
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
string toBin(int n, int l) {
string s(l, '0');
for(int i=0;i<l;i++)
s[i] = !!(n & (1 << i)) + '0';
return s;
}
int toDec(string s) {
reverse(s.begin(),s.end());
int ans = 0;
for(auto i: s)
ans = (ans << 1) | (i & 1);
return ans;
}
int x, y;
}
std::string SendB(int N, int X, int Y) {
x = X, y = Y;
return toBin(100 * (X / 2) + (Y / 200), 20);
}
int Answer(std::string T) {
int bad = toDec(T.substr(0,8)) + 200 * (y / 200);
int ans = toDec(T.substr(8,14)) + (x&1?(T[22]&1?1:-1):0);
for(int i=0;i<(y%200);i++) {
if((x & 1) && (y - (y % 200) + i == x - 1 || y - (y % 200) + i == bad))
ans += ((T[i+23]&1)?-1:1);
else
ans += ((T[i+23]&1)?1:-1);
}
return ans;
}
