#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "Azer.h"
const int INF = 1e9 + 69;
struct Edge{
int u, v, w;
Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};
struct P{
int i, w;
P(int i = 0, int w = 0): i(i), w(w){}
};
struct compare{
bool operator () (P a, P b){return a.w > b.w;}
};
P DecodeSignal(vector<bool> signal){
P ans;
for(int i = 0; i< 11; ++i) ans.i += signal[i] * MASK(i);
for(int i = 0; i< 20; ++i) ans.w += signal[i+11] * MASK(i);
return ans;
}
int n1;
vector<bool> infoA;
vector<vector<P>> graph1;
vector<bool> visited1;
vector<int> dihh1;
priority_queue<P, vector<P>, compare> pq1;
void SendSignalA(P v){
bitset<11> u(v.i);
bitset<20> w(v.w);
for(int i = 0; i < 11; ++i) SendA(u[i]);
for(int i = 0; i < 20; ++i) SendA(w[i]);
}
void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> w){
n1 = n;
infoA.clear(); graph1.clear(); visited1.clear(); dihh1.clear();
while(pq1.size()) pq1.pop();
graph1.resize(n);
for(int i = 0; i < m; ++i){
graph1[u[i]].push_back(P(v[i], w[i]));
graph1[v[i]].push_back(P(u[i], w[i]));
}
visited1.resize(n); dihh1.resize(n, INF);
dihh1[0] = 0;
visited1[0] = 1;
pq1.push(P(2047, MASK(20) - 1));
for(P v: graph1[0]) if (minimize(dihh1[v.i], dihh1[0] + v.w))
pq1.push(P(v.i, dihh1[v.i]));
SendSignalA(pq1.top());
}
void ReceiveA(bool x){
infoA.push_back(x);
if (infoA.size() == 31){
P cur = DecodeSignal(infoA);
infoA.clear();
// cout << "A received: " << cur.i << " " << cur.w << endl;
// printArr(visited1);
pq1.push(cur);
P u = pq1.top(); pq1.pop();
if (u.i >= n1) return;
if (!visited1[u.i]) {
visited1[u.i] = true;
minimize(dihh1[u.i], u.w);
for(P v: graph1[u.i])
if (minimize(dihh1[v.i], dihh1[u.i] + v.w))
pq1.push(P(v.i, dihh1[v.i]));
}
while(true){
P u = pq1.top();
if (u.i >= n1) break;
if (visited1[u.i])
pq1.pop();
else break;
}
SendSignalA(pq1.top());
}
}
vector<int> Answer(){
return dihh1;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "Baijan.h"
const int INF = 1e9 + 69;
struct Edge{
int u, v, w;
Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};
struct P{
int i, w;
P(int i = 0, int w = 0): i(i), w(w){}
};
struct compare{
bool operator () (P a, P b){return a.w > b.w;}
};
P DecodeSignal(vector<bool> signal){
P ans;
for(int i = 0; i< 11; ++i) ans.i += signal[i] * MASK(i);
for(int i = 0; i< 20; ++i) ans.w += signal[i+11] * MASK(i);
return ans;
}
int n2;
vector<bool> infoB;
vector<vector<P>> graph2;
vector<bool> visited2;
vector<int> dihh2;
priority_queue<P, vector<P>, compare> pq2;
void SendSignalB(P v){
bitset<11> u(v.i);
bitset<20> w(v.w);
for(int i = 0; i < 11; ++i) SendB(u[i]);
for(int i = 0; i < 20; ++i) SendB(w[i]);
}
void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> w){
n2 = n;
infoB.clear(); graph2.clear(); visited2.clear(); dihh2.clear();
while(pq2.size()) pq2.pop();
graph2.resize(n);
for(int i = 0; i < m; ++i){
graph2[u[i]].push_back(P(v[i], w[i]));
graph2[v[i]].push_back(P(u[i], w[i]));
}
visited2.resize(n); dihh2.resize(n, INF);
dihh2[0] = 0;
visited2[0] = 1;
pq2.push(P(2047, MASK(20) - 1));
for(P v: graph2[0]) if (minimize(dihh2[v.i], dihh2[0] + v.w))
pq2.push(P(v.i, dihh2[v.i]));
SendSignalB(pq2.top());
}
void ReceiveB(bool x){
infoB.push_back(x);
if (infoB.size() == 31){
P cur = DecodeSignal(infoB);
infoB.clear();
// cout << "B received: " << cur.i << " " << cur.w << endl;
// printArr(visited2);
pq2.push(cur);
P u = pq2.top(); pq2.pop();
if (u.i >= n2) return;
if (!visited2[u.i]){
visited2[u.i] = true;
minimize(dihh2[u.i], u.w);
for(P v: graph2[u.i])
if (minimize(dihh2[v.i], dihh2[u.i] + v.w))
pq2.push(P(v.i, dihh2[v.i]));
}
while(true){
P u = pq2.top();
if (u.i >= n2) break;
if (visited2[u.i])
pq2.pop();
else break;
}
SendSignalB(pq2.top());
}
}
