#include "Aoi.h"
#include "bits/stdc++.h"
namespace {
using namespace std;
using ll = long long;
const ll inf = 1e18;
int variable_example = 0;
int function_example(int a, int b) { return a + b; }
} // namespace
std::string aoi(int n, int m, int q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> w, std::vector<int> T, std::vector<int> X) {
sort(X.begin(), X.end());
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[A[i]].emplace_back(B[i], i);
g[B[i]].emplace_back(A[i], i);
}
auto get = [&](int to) -> vector<int> {
vector<ll> dist(n, inf);
vector<pair<int, int>> par(n);
priority_queue<pair<ll, int>> pq;
dist[0] = 0; pq.emplace(0, 0);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (dist[u] < -d) continue;
for (auto [v, i]: g[u]) {
if (dist[v] <= dist[u] + w[i]) continue;
dist[v] = dist[u] + w[i];
par[v] = make_pair(u, i);
pq.emplace(-dist[v], v);
}
}
int now = to;
vector<int> ans;
while (now != 0) {
ans.emplace_back(par[now].second);
now = par[now].first;
}
reverse(ans.begin(), ans.end());
return ans;
};
vector<int> id(m, -1);
for (int i = 0; i < K; i++) id[X[i]] = i;
string ans(40 * K, '0');
for (int i = 0; i < K; i++) {
for (int j = 0; j < 40; j++) {
// cout << w[X[i]] << ' ' << j << ' ' << (w[X[i]] >> j & 1ll) << endl;
ans[i * 40 + j] = (w[X[i]] >> j & 1ll) + '0';
}
}
// for (int i = 0; i < q; i++) {
// auto way = get(T[i]);
// for (int pos: way) {
// if (id[pos] != -1) ans[i * K + id[pos]] = '1';
// }
// }
return ans;
}
#include "Bitaro.h"
#include "bits/stdc++.h"
namespace {
using namespace std;
using ll = long long;
const ll inf = 1e18;
int variable_example = 0;
int function_example(int a, int b) { return a + b; }
} // namespace
void bitaro(int n, int m, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> w, std::vector<int> T, std::vector<int> X, std::string s) {
sort(X.begin(), X.end());
// cout << '\t' << s << endl;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
g[A[i]].emplace_back(B[i], i);
g[B[i]].emplace_back(A[i], i);
}
for (int i = 0; i < K; i++) {
w[X[i]] = 0;
for (int j = 0; j < 40; j++) w[X[i]] += (ll((s[i * 40 + j] - '0'))) << j;
}
// vector<bool> can(m);
// vector<int> id(m, -1);
// for (int i = 0; i < K; i++) id[X[i]] = i;
auto get = [&](int to) -> vector<int> {
vector<ll> dist(n, inf);
vector<pair<int, int>> par(n);
priority_queue<pair<ll, int>> pq;
dist[0] = 0; pq.emplace(0, 0);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (dist[u] < -d) continue;
for (auto [v, i]: g[u]) {
ll now = dist[u];
// if (id[i] == -1) now += w[i];
// else now += can[i] ? 0 : inf;
now += w[i];
if (dist[v] <= dist[u] + now) continue;
dist[v] = dist[u] + now;
par[v] = make_pair(u, i);
pq.emplace(-dist[v], v);
}
}
int now = to;
vector<int> ans;
while (now != 0) {
ans.emplace_back(par[now].second);
now = par[now].first;
}
reverse(ans.begin(), ans.end());
return ans;
};
for (int i = 0; i < Q; i++) {
// for (int j = 0; j < K; j++) can[X[j]] = s[i * K + j] - '0';
auto way = get(T[i]);
// for (int j = 0; j < K; j++) can[X[j]] = false;
answer(way);
}
}
