#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
namespace {
}
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) {
string ret;
for (const auto &i : X)
FOR(j, 0, 39)
ret.push_back('0' + ((C[i] & 1ll << j) > 0));
return ret;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
namespace {
} // namespace
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) {
FOR(i, 0, K-1) {
C[X[i]] = 0;
FOR(j, 0, 39)
C[X[i]] |= ll(s[40*i+j] - '0') << j;
}
vt<vt<ari2>> adj(N);
FOR(i, 0, M-1) {
adj[A[i]].push_back({B[i], i});
adj[B[i]].push_back({A[i], i});
}
vt<ll> dist(N, LLONG_MAX);
vt<int> back(N);
priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
pq.push({dist[0] = 0, 0});
while (size(pq)) {
const auto [d, i] = pq.top();
pq.pop();
if (d > dist[i]) continue;
for (const auto &[j, e] : adj[i])
if (d + C[e] < dist[j]) {
pq.push({dist[j] = d + C[e], j});
back[j] = e;
}
}
for (const auto &x : T) {
vt<int> ans;
for (int cur = x; cur; cur = A[back[cur]] ^ B[back[cur]] ^ cur)
ans.push_back(back[cur]);
reverse(all(ans));
#ifdef DEBUG
cout << x << '\n';
for (const auto &i : ans)
cout << i << ' ';
cout << '\n';
#endif
answer(ans);
}
}
