#include "Aoi.h"
#include <iostream>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
std::vector<int> B, std::vector<long long> C,
std::vector<int> T, std::vector<int> X) {
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
vector <ll> dist, P, E, virtualP;
string S;
ll missingedge[20000], G[300];
vector <array<ll, 3>> adj[10000];
dist.resize(N);
P.resize(N);
virtualP.resize(K);
E.resize(N);
for (int i=0; i<N; ++i) dist[i] = (ll)1e18, P[i] = -1;
for (int i=0; i<M; ++i) {
missingedge[i] = -1;
adj[A[i]].push_back({B[i], C[i], i});
adj[B[i]].push_back({A[i], C[i], i});
}
for (int i=0; i<K; ++i) G[i] = -1, virtualP[i] = -1;
for (int i=0; i<X.size(); ++i) missingedge[X[i]] = i;
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, x, id] : adj[u]) {
if (dist[v] > dist[u] + x) {
dist[v] = dist[u] + x;
P[v] = u;
E[v] = id;
pq.push({dist[v], v});
}
}
}
array<ll, 2> cnt[17];
vector <ll> st, pv;
for (int i=0; i<17; ++i) cnt[i] = {0, i};
for (int i=0; i<Q; ++i) {
ll u = T[i];
vector <ll> V;
while (u) {
if (missingedge[E[u]] != -1) {
if (G[missingedge[E[u]]] == -1) G[missingedge[E[u]]] = i;
V.push_back(missingedge[E[u]]);
}
u = P[u];
}
if (V.empty()) st.push_back(-1), pv.push_back(-1);
else {
if (G[V[0]] != i) st.push_back(-1), pv.push_back(V[0]);
if (G[V.back()] == i) st.push_back(V.back()), pv.push_back(-1);
}
for (int j=0; j+1<V.size(); ++j) {
if (G[V[j]] == i && G[V[j+1]] != i) st.push_back(V[j]), pv.push_back(V[j+1]);
if (virtualP[V[j]] == -1) virtualP[V[j]] = V[j+1];
}
}
for (int i=0; i<K; ++i) ++cnt[G[i] == -1 ? 16 : G[i]][0];
sort(cnt, cnt+17, [](auto a, auto b) {
return a[0] < b[0];
});
if (cnt[0][1] > cnt[1][1]) swap(cnt[0], cnt[1]);
for (int i=0; i<2; ++i) {
for (int k=4; k>=0; --k) S += char('0'+min(1LL, cnt[i][1]&(1LL<<k)));
}
for (int i=0; i<K; ++i) {
ll u = G[i] == -1 ? 16 : G[i];
if (u == cnt[0][1]) S += "11110";
else if (u == cnt[1][1]) S += "11111";
else {
if (u >= cnt[1][1]) --u;
if (u >= cnt[0][1]) --u;
for (int k=3; k>=0; --k) S += char('0'+min(1LL, u&(1LL<<k)));
}
}
for (int i=0; i<Q; ++i) {
if (st[i] == -1) S += "111111111";
else {
for (int k=8; k>=0; --k) S += char('0'+min(1LL, st[i]&(1LL<<k)));
}
if (pv[i] == -1) S += "111111111";
else {
for (int k=8; k>=0; --k) S += char('0'+min(1LL, pv[i]&(1LL<<k)));
}
}
return S;
}
#include "Bitaro.h"
#include <iostream>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long
using namespace std;
namespace{
vector <int> path[16];
vector <ll> dist, dist2[16], P, E, Z, H[300];
vector <array<ll, 2>> edgedir;
priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq;
vector <array<ll, 3>> adj[10000];
void append(vector <int> &A, vector <ll> B) {
for (auto u : B) A.push_back(u);
}
void append(vector <int> &A, vector <int> B) {
for (auto u : B) A.push_back(u);
}
vector <ll> query(ll a, ll b, ll c) {
for (int i=0; i<dist.size(); ++i) dist[i] = (ll)1e18, P[i] = E[i] = -1;
dist[a] = 0;
pq.push({0, a});
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, x, id] : adj[u]) {
if (x == (ll)1e18 || dist[v] <= dist[u]+x) continue;
dist[v] = dist[u] + x;
P[v] = u, E[v] = id;
pq.push({dist[v], v});
}
}
if (dist[b] > dist[c]) b = c;
vector <ll> edge;
while (b != a) {
edge.push_back(E[b]);
b = P[b];
}
reverse(edge.begin(), edge.end());
return edge;
}
}
void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
std::vector<long long> C, std::vector<int> T, std::vector<int> X,
std::string S) {
vector <ll> G, en;
edgedir.resize(M);
Z.resize(M);
dist.resize(N);
for (int i=0; i<Q; ++i) dist2[i].resize(N);
P.resize(N);
E.resize(N);
G.resize(K);
en.resize(K);
for (auto u : X) C[u] = (ll)1e18;
for (int i=0; i<M; ++i) {
edgedir[i] = {-1, -1};
Z[i] = -1;
adj[A[i]].push_back({B[i], C[i], i});
adj[B[i]].push_back({A[i], C[i], i});
}
for (int i=0; i<X.size(); ++i) Z[X[i]] = i;
int pt = 0;
vector <ll> U;
for (int i=0; i<2; ++i) {
ll cur = 0;
for (int k=4; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
U.push_back(cur);
}
for (int i=0; i<K; ++i) {
en[i] = -1;
ll cur = 0;
for (int k=3; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
if (cur == 15) {
if (S[pt++] == '0') G[i] = (U[0] == 16 ? -1 : U[0]);
else G[i] = (U[1] == 16 ? -1 : U[1]);
}
else {
if (cur >= U[0]) ++cur;
if (cur >= U[1]) ++cur;
G[i] = (cur == 16 ? -1 : cur);
}
}
vector <ll> st, pv, rt;
for (int i=0; i<Q; ++i) {
ll cur = 0;
for (int k=8; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
st.push_back(cur == (1LL<<9)-1 ? -1 : cur);
cur = 0;
for (int k=8; k>=0; --k) cur += (S[pt++]-'0') * (1LL<<k);
pv.push_back(cur == (1LL<<9)-1 ? -1 : cur);
rt.push_back(-1);
if (pv[i] != -1) H[pv[i]].push_back(i);
if (pv[i] == -1 && st[i] == -1) append(path[i], vector<ll>{query(0, T[i], T[i])});
else if (pv[i] == -1) {
append(path[i], vector<ll>{query(0, A[X[st[i]]], B[X[st[i]]])});
path[i].push_back(X[st[i]]);
if (dist[A[X[st[i]]]] > dist[B[X[st[i]]]]) rt[i] = A[X[st[i]]];
else rt[i] = B[X[st[i]]];
}
}
for (int i=0; i<Q; ++i) {
for (int j=0; j<N; ++j) dist[j] = (ll)1e18, P[j] = -1, E[j] = -1;
if (pv[i] == -1 && st[i] == -1) {
answer(path[i]);
continue;
}
dist[rt[i]] = 0;
pq.push({0, rt[i]});
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist[u] != w) continue;
for (auto [v, x, id] : adj[u]) {
if (x == (ll)1e18) {
if (Z[id] != -1 && G[Z[id]] == i && dist[v] > dist[u]+1) {
dist[v] = dist[u]+1;
P[v] = u, E[v] = id;
pq.push({dist[v], v});
}
}
else if (dist[v] > dist[u]+x) {
dist[v] = dist[u]+x;
P[v] = u, E[v] = id;
pq.push({dist[v], v});
}
}
}
vector <ll> tmp;
ll u = T[i];
while (u != rt[i]) {
tmp.push_back(E[u]);
u = P[u];
}
reverse(tmp.begin(), tmp.end());
append(path[i], tmp);
answer(path[i]);
u = T[i];
while (!path[i].empty()) {
if (Z[path[i].back()] != -1) {
if (G[Z[path[i].back()]] != i) break;
for (auto z : H[Z[path[i].back()]]) {
append(path[z], path[i]);
rt[z] = u;
}
}
if (u == rt[i]) break;
u = (u == A[path[i].back()] ? B[path[i].back()] : A[path[i].back()]);
path[i].pop_back();
}
}
}
