#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
namespace {
const int lg=40;
} // namespace
string aoi(int N, int M, int Q, int K, vector<int> A,vector<int> B, vector<long long> C,
vector<int> T,vector<int> X) {
string s="";
for(int i:X){
ll len=C[i];
cerr<<len<<' ';
for(int j=0;j<lg;j++){
if(len&(1ll<<j)){
s+='1';
}
else{
s+='0';
}
}
}
// cerr<<endl;
// cerr<<s<<endl;
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
namespace {
const int lg=40,maxn=1e4+5;
int N,M;
int from[maxn],edge[maxn];
long long dist[maxn];
vector<tuple<int,ll,int>>g[maxn];
void dijkstra(){
fill(dist,dist+N,(ll)1e18);
set<pair<ll,int>>st;
st.insert({0,0});
dist[0]=0;
while(!st.empty()){
ll D=st.begin()->ff,i=st.begin()->ss;
st.erase(st.begin());
if(dist[i]!=D) continue;
for(auto [j,w,e]:g[i]){
if(dist[i]+w<dist[j]){
edge[j]=e;
from[j]=i;
dist[j]=dist[i]+w;
st.insert({dist[j],j});
}
}
}
// for(int i=0;i<N;i++){
// cerr<<dist[i]<<' ';
// }
// cerr<<endl;
return;
}
} // namespace
void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B,
vector<long long> C, vector<int> T, vector<int> X,string s) {
::N=N;
::M=M;
for(int i=0;i<K;i++){
ll len=0;
for(int j=0;j<lg;j++){
if(s[i*lg+j]=='1') len+=(1ll<<j);
}
C[X[i]]=len;
// cerr<<len<<endl;
}
for(int i=0;i<M;i++){
g[A[i]].pb({B[i],C[i],i});
g[B[i]].pb({A[i],C[i],i});
}
dijkstra();
for(int u:T){
vector<int>path;
int cur=u;
while(cur!=0){
path.pb(edge[cur]);
cur=from[cur];
}
reverse(all(path));
answer(path);
}
return;
}
