#include<bits/stdc++.h>
#define MAXN 20007
#include "Aoi.h"
using namespace std;
const long long inf=1e17;
int n,m,k,q,parent[MAXN],up[MAXN],where[MAXN];
long long cost[MAXN],dist[MAXN];
vector< pair<int,int> > v[MAXN],tree[MAXN];
bool vis[MAXN],special[MAXN],rem[MAXN];
string ans;
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > pq;
void dijkstra(int x){
for(int i=1;i<=n;i++)dist[i]=inf;
dist[x]=0;
pq.push({dist[x],x});
while(!pq.empty()){
int minv=pq.top().second;
pq.pop();
if(vis[minv])continue;
vis[minv]=true;
for(auto e:v[minv]){
if(vis[e.first] or dist[e.first]<=dist[minv]+cost[e.second])continue;
dist[e.first]=dist[minv]+cost[e.second];
parent[e.first]=minv;
up[e.first]=e.second;
pq.push({dist[e.first],e.first});
}
}
}
vector<int> path;
string num(int x,int bits){
string res;
for(int i=0;i<bits;i++){
res.push_back(x%2+'0');
x/=2;
}
reverse(res.begin(),res.end());
return res;
}
void dfs(int x){
if(special[x])where[x]=path.back();
for(auto e:tree[x]){
if(rem[e.second]){
up[e.second]=path.back();
path.push_back(e.second);
}
dfs(e.first);
if(rem[e.second])path.pop_back();
}
}
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){
n=N; m=M; q=Q; k=K;
for(int i=1;i<=q;i++){
special[T[i-1]+1]=true;
}
for(int i:X)rem[i+1]=true;
for(int i=1;i<=m;i++){
v[A[i-1]+1].push_back({B[i-1]+1,i});
v[B[i-1]+1].push_back({A[i-1]+1,i});
}
for(int i=1;i<=m;i++)cost[i]=C[i-1];
dijkstra(1);
for(int i=2;i<=n;i++){
tree[parent[i]].push_back({i,up[i]});
}
path={0};
dfs(1);
for(int i=1;i<=q;i++){
ans+=num(where[T[i-1]+1],9);
}
for(int i=1;i<=k;i++){
ans+=num(up[X[i-1]+1],9);
}
return ans;
}
#include<bits/stdc++.h>
#define MAXN 20007
#include "Bitaro.h"
using namespace std;
const long long inff=1e17;
int nn,mm,kk,qt;
int comp[MAXN],par[MAXN],who[MAXN];
bool miss[MAXN];
vector< pair<int,int> > w[MAXN];
vector<int> t[MAXN];
long long edge[MAXN],dst[607][MAXN];
pair<int,int> to[607][MAXN];
bool used[MAXN];
vector<int> qs[MAXN];
priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > qq;
void dijkstra(int id,int x){
for(int i=1;i<=nn;i++)dst[id][i]=inff;
dst[id][x]=0;
qq.push({dst[id][x],x});
while(!qq.empty()){
int minv=qq.top().second;
qq.pop();
if(used[minv])continue;
used[minv]=true;
for(auto e:w[minv]){
if(used[e.first] or dst[id][e.first]<=dst[id][minv]+edge[e.second])continue;
dst[id][e.first]=dst[id][minv]+edge[e.second];
to[id][e.first]={minv,e.second};
qq.push({dst[id][e.first],e.first});
}
}
}
vector<int> sol[MAXN];
pair<int,int> z[MAXN];
vector<int> route(int id,int x){
vector<int> s;
while(to[id][x].first!=0){
s.push_back(to[id][x].second);
x=to[id][x].first;
}
reverse(s.begin(),s.end());
return s;
}
vector<int> mergev(vector<int> x,vector<int> y){
for(int i=0;i<y.size();i++){
x.push_back(y[i]);
}
return x;
}
void fix(int x){
int from=0;
if(x==0)from=0;
else from=x+kk;
for(int i:t[x]){
if(dst[from][z[i].second] < dst[from][z[i].first]){
swap(z[i].first,z[i].second);
for(int f=1;f<=nn;f++)swap(dst[i][f],dst[i+kk][f]);
}
fix(i);
}
}
void solve(int x,vector<int> path){
int id=0;
if(x>0)id=kk+x;
for(int i:qs[x]){
sol[i]=mergev(path,route(id,i));
}
for(int i:t[x]){
solve(i,mergev(mergev(path,{who[i]}),route(id,z[i].first)) );
}
}
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){
nn=N; mm=M; kk=K; qt=Q;
for(int i:X)miss[i+1]=true;
for(int i=1;i<=mm;i++){
if(miss[i])continue;
w[A[i-1]+1].push_back({B[i-1]+1,i});
w[B[i-1]+1].push_back({A[i-1]+1,i});
edge[i]=C[i-1];
}
z[0]={1,1};
dijkstra(0,1);
for(int i=0;i<X.size();i++){
z[i+1]={A[X[i]]+1,B[X[i]]+1};
dijkstra(i+1,A[X[i]]+1);
dijkstra(i+1+kk,B[X[i]]+1);
who[i+1]=X[i]+1;
}
for(int i=0;i<9*qt;i+=9){
int curr=0;
for(int f=i;f<i+9;f++){
curr*=2; curr+=s[f]-'0';
}
qs[curr].push_back(T[i/9]+1);
}
for(int i=qt*9;i<s.size();i+=9){
int curr=0;
for(int f=i;f<i+9;f++){
curr*=2; curr+=s[f]-'0';
}
par[(i-9*qt)/9+1]=curr;
}
for(int i=1;i<=kk;i++){
t[par[i]].push_back(i);
}
fix(0);
solve(0,{});
for(int i:T){
for(int &f:sol[i+1])f--;
answer(sol[i+1]);
}
return;
}
