#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
namespace {
ll INF = 1e18;
bool cont(ll x, ll i) {
return (x & (1ll << i)) != 0;
}
struct Ed {
ll v, id;
};
ll V, E, q, k;
vc<vc<Ed>> g;
vc<ll> wgh, qus, a, d;
vc<Ed> p;
vc<ll> wh, par;
void dijkstra() {
p.resize(V);
d.assign(V, INF);
d[0] = 0;
priority_queue<pll, vc<pll>, greater<>> pq;
pq.push({d[0], 0});
while (not pq.empty()) {
ll dv = pq.top().st;
ll v = pq.top().nd;
pq.pop();
if (d[v] != dv)
continue;
for (auto &[w, id] : g[v]) {
ll dw = dv + wgh[id];
if (dw < d[w]) {
d[w] = dw;
p[w] = {v, id};
pq.push({dw, w});
}
}
}
}
void track() {
wh.assign(k, 16);
par.assign(q, k);
for (ll i = 0; i < q; i++) {
ll v = qus[i];
while (v != 0) {
ll id = p[v].id;
if (a[id] != -1 and wh[a[id]] == 16)
wh[a[id]] = i;
else if (a[id] != -1) {
par[i] = a[id];
break;
}
v = p[v].v;
}
}
}
string generate() {
string ret;
for (ll i = 0; i < k; i += 6) {
ll x = 0;
for (ll j = i; j < i + 6; j++) {
x *= 17;
if (j < k)
x += wh[j];
}
for (ll j = 0; j < 25; j++)
if (cont(x, j))
ret.pub('1');
else
ret.pub('0');
}
for (ll i = 1; i < q; i++) {
for (ll j = 0; j < 9; j++)
if (cont(par[i], j))
ret.pub('1');
else
ret.pub('0');
}
return ret;
}
string code() {
dijkstra();
track();
return generate();
}
}
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) {
V = N;
E = M;
q = Q;
k = K;
g.assign(V, vc<Ed>());
for (ll i = 0; i < E; i++) {
g[A[i]].pub({B[i], i});
g[B[i]].pub({A[i], i});
}
wgh = C;
qus = vc<ll>(all(T));
a.assign(E, -1);
for (ll i = 0; i < k; i++)
a[X[i]] = i;
return code();
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;
namespace {
ll ceil(ll x, ll y) {
return (x + y - 1) / y;
}
struct Ed {
ll v, id;
};
struct Node {
ll par, id;
};
ll V, E, q, k;
vc<vc<Ed>> g;
vc<ll> wgh, qus, a, isa;
vc<Node> t;
vc<ll> wh, par, pos;
string str;
vc<ll> d;
vc<Ed> p;
void decode() {
wh.resize(k);
for (ll i = 0; i < ceil(k, 6); i++) {
ll x = 0;
for (ll j = 0; j < 25; j++)
x |= (1ll << j) * (str[25 * i + j] == '1');
for (ll j = 6 * i + 5; j >= 6 * i; j--) {
if (j < k)
wh[j] = x % 17;
x /= 17;
}
}
par.assign(q, 0);
par[0] = k;
for (ll i = 1; i < q; i++) {
for (ll j = 0; j < 9; j++)
par[i] |= (1ll << j) * (str[ceil(k, 6) * 6 + i * 9 + j] == '1');
}
}
void dijkstra() {
p.resize(V);
d.assign(V, INF);
d[0] = 0;
priority_queue<pll, vc<pll>, greater<>> pq;
pq.push({d[0], 0});
while (not pq.empty()) {
ll dv = pq.top().st;
ll v = pq.top().nd;
pq.pop();
if (dv != d[v])
continue;
for (auto &[w, id] : g[v]) {
ll dw = dv + wgh[id];
if (dw < d[w]) {
d[w] = dw;
p[w] = {v, id};
pq.push({d[w], w});
}
}
}
}
void tracks() {
t.pub({-1, -1});
pos.resize(k + 1);
pos[k] = 0;
for (ll i = 0; i < q; i++) {
for (ll j = 0; j < k; j++)
if (wh[j] == i)
wgh[a[j]] = 0;
else
wgh[a[j]] = INF;
ll v = pos[par[i]];
while (v != 0) {
wgh[a[t[v].id]] = 0;
v = t[v].par;
}
dijkstra();
vc<ll> pth;
v = qus[i];
vc<int> ret;
while (v != 0) {
ll e = p[v].id;
if (isa[e] != -1 and wh[isa[e]] != i)
break;
if (isa[e] != -1 and wh[isa[e]] == i) {
pth.pub(isa[e]);
pos[isa[e]] = sz(t);
t.pub({-1, isa[e]});
}
ret.pub((int)p[v].id);
v = p[v].v;
}
for (ll j = 0; j + 1 < sz(pth); j++)
t[pos[j]].par = pos[j + 1];
t[pos.back()].par = pos[par[i]];
reverse(all(ret));
answer(ret);
}
}
}
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) {
V = N;
E = M;
q = Q;
k = K;
g.assign(V, vc<Ed>());
for (ll i = 0; i < E; i++) {
g[A[i]].pub({B[i], i});
g[B[i]].pub({A[i], i});
}
wgh = C;
qus = vc<ll>(all(T));
a = vc<ll>(all(X));
isa.assign(E, -1);
for (ll i = 0; i < k; i++)
isa[a[i]] = i;
str = s;
decode();
tracks();
}
