#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
// HL 分解, 上から順に二分探索
string solve(int N, int R, vector<int> U, vector<int> V) {
const int M = N * 2 + 1;
string ans(N, '&');
string s_(M, '0');
auto Query = [&](string s) {
assert((int)s.size() == M);
for (int i = 0; i < M; i++) {
s[i] ^= s_[i] & 1;
}
return query(s);
};
auto Flip = [&](int i) {
ans[i] ^= '|' ^ '&';
s_[i] ^= 1;
s_[U[i]] ^= 1;
s_[V[i]] ^= 1;
};
// HL 分解
vector<int> siz(M, 0);
for (int i = N; i--; ) {
const int u = U[i], v = V[i];
if (siz[u] < siz[v]) {
swap(U[i], V[i]);
}
siz[i] = siz[u] + siz[v] + 1;
}
// light-edge の深さで頂点を分類
vector<int> depth(M, 0);
for (int i = 0; i < N; i++) {
const int u = U[i], v = V[i];
depth[u] = depth[i];
depth[v] = depth[i] + 1;
}
// 深さごとに頂点のリストを作る
const int D = ranges::max(depth | views::take(N)) + 1;
vector<vector<int>> Chain(D);
for (int i = 0; i < N; i++) {
Chain[depth[i]].push_back(i);
}
// 深さごとに二分探索
for (const auto& chain : Chain) {
// chain[:r] に 1 個ずつ入力を与えて 1 が出力されるか
auto check = [&](int r) {
string s(M, '0');
for (int i : chain | views::take(r)) {
s[V[i]] = '1';
}
return Query(s);
};
// 二分探索の幅を 64 に制限
const int w = 64;
const int R = chain.size();
for (int L0 = 0, R0 = w; L0 < R; L0 += w, R0 += w) {
R0 = min(R0, R);
while (check(R0)) {
int zero = L0, one = R0;
while (one - zero > 1) {
const int mid = (zero + one) / 2;
(check(mid) ? one : zero) = mid;
}
Flip(chain[zero]);
}
}
// 全部 OR にする
for (int i : chain) {
s_[i] ^= 1;
s_[U[i]] ^= 1;
s_[V[i]] ^= 1;
}
}
return ans;
}
