#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
namespace {
int n,m,q,k;
vector<ii> al[20005];
int w[20005];
int hidden[20005];
vector<ii> al2[20005];
ii pp[20005];
int d[20005];
int typ[20005];
int CNT=2;
int ID[1<<16];
string bs;
int inf[305];
int CNT2=0;
int posq[35];
void dfs(int i){
bool f=false;
if (ID[typ[i]]==-1){
ID[typ[i]]=CNT++;
f=true;
bs+="0";
}
if (n<=i){
//cout<<i<<" "<<ID[typ[i]]<<endl;
posq[i-n]=CNT2++;
}
for (auto [it,id]:al2[i]) if ((typ[it])&1){
if (typ[it]){
dfs(it);
if (hidden[id]!=-1) inf[hidden[id]]=ID[typ[it]];
//if (typ[it]!=typ[i]) cout<<"? "<<ID[typ[i]]<<" "<<ID[typ[it]]<<endl;
}
}
for (auto [it,id]:al2[i]) if ((~typ[it])&1){
if (typ[it]){
dfs(it);
if (hidden[id]!=-1) inf[hidden[id]]=ID[typ[it]];
//if (typ[it]!=typ[i]) cout<<"? "<<ID[typ[i]]<<" "<<ID[typ[it]]<<endl;
}
}
if (f) bs+="1";
}
} // namespace
std::string aoi(signed N, signed M, signed Q, signed K, std::vector<signed> A,
std::vector<signed> B, std::vector<long long> C,
std::vector<signed> T, std::vector<signed> X) {
n=N,m=M,q=Q,k=K;
rep(x,0,m){
al[A[x]].pub({B[x],x});
al[B[x]].pub({A[x],x});
w[x]=C[x];
}
memset(hidden,-1,sizeof(hidden));
rep(x,0,k) hidden[X[x]]=x;
priority_queue<ii,vector<ii>,greater<ii> > pq;
memset(d,63,sizeof(d));
d[0]=0;
pq.push({d[0],0});
while (!pq.empty()){
int u,ww; tie(ww,u)=pq.top(); pq.pop();
if (d[u]!=ww) continue;
for (auto [it,id]:al[u]) if (d[it]>ww+w[id]){
d[it]=ww+w[id];
pq.push({d[it],it});
pp[it]={u,id};
}
}
rep(x,1,n) al2[pp[x].fi].pub({x,pp[x].se});
rep(x,0,q){
int curr=T[x];
while (curr){
typ[curr]|=1<<x;
curr=pp[curr].fi;
}
al2[T[x]].pub({n+x,20004});
typ[n+x]=1<<x;
}
memset(ID,-1,sizeof(ID));
typ[0]=(1<<q)-1;
ID[(1<<q)-1]=1;
dfs(0);
//rep(x,0,n) cout<<typ[x]<<" "; cout<<endl;
//rep(x,0,k) cout<<inf[x]<<" "; cout<<endl;
string s;
rep(x,0,k){
rep(i,0,5) s+='0'+((inf[x]>>i)&1);
}
rep(x,1,q){
//cout<<d[T[x]]<<endl;
rep(i,0,4) s+='0'+((posq[x]>>i)&1);
}
if (bs=="") bs="01";
return s+bs.substr(1,sz(bs)-2);
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
namespace {
int n,m,q,k;
vector<ii> al[10005];
int w[20005];
vector<int> imp;
int rit[10005];
int d[610][10005];
ii pp[610][10005];
void add(int u){
int i=sz(imp);
rit[u]=i;
imp.pub(u);
priority_queue<ii,vector<ii>,greater<ii> > pq;
memset(d[i],63,sizeof(d[i]));
d[i][u]=0;
pq.push({d[i][u],u});
while (!pq.empty()){
int u,ww; tie(ww,u)=pq.top(); pq.pop();
if (d[i][u]!=ww) continue;
for (auto [it,id]:al[u]) if (d[i][it]>ww+w[id]){
d[i][it]=ww+w[id];
pq.push({d[i][it],it});
pp[i][it]={u,id};
}
}
}
int inf[305];
int sp[50];
ii PP[10005]; //this guys contains the actual answers
int RR[50];
} // namespace
void bitaro(signed N, signed M, signed Q, signed K, std::vector<signed> A, std::vector<signed> B,
std::vector<long long> C, std::vector<signed> T, std::vector<signed> X,
std::string s) {
n=N,m=M,q=Q,k=K;
rep(x,0,m) if (C[x]!=-1){
al[A[x]].pub({B[x],x});
al[B[x]].pub({A[x],x});
w[x]=C[x];
}
memset(rit,-1,sizeof(rit));
add(0);
rep(x,0,k){
rep(i,0,5) if (s[x*5+i]=='1') inf[x]+=1<<i;
}
int currn=2;
vector<int> stk={1};
string bs="0"+s.substr(k*5+(q-1)*4,sz(s)-(k*5+(q-1)*4))+"1";
sp[1]=0;
for (auto it:bs){
if (it=='0'){
sp[currn]=stk.back();
stk.pub(currn++);
}
else{
stk.pob();
}
}
vector<int> LL;
rep(x,1,currn){
bool leaf=true;
rep(y,1,currn) if (sp[y]==x) leaf=false;
if (leaf) LL.pub(x);
}
//for (auto it:LL) cout<<it<<" "; cout<<endl;
RR[0]=0;
add(0);
rep(x,1,currn){
set<int> st;
rep(y,0,k) if (inf[y]==x) st.insert(y);
int R=RR[sp[x]];
while (!st.empty()){
int mn=1e18;
for (auto it:st){
mn=min(mn,d[rit[R]][A[X[it]]]);
mn=min(mn,d[rit[R]][B[X[it]]]);
}
for (auto it:st){
if (mn==d[rit[R]][A[X[it]]]){
int curr=A[X[it]];
while (curr!=R){
PP[curr]={pp[rit[R]][curr].fi,pp[rit[R]][curr].se};
curr=pp[rit[R]][curr].fi;
}
PP[B[X[it]]]={A[X[it]],X[it]};
R=B[X[it]];
st.erase(it);
break;
}
if (mn==d[rit[R]][B[X[it]]]){
int curr=B[X[it]];
while (curr!=R){
PP[curr]={pp[rit[R]][curr].fi,pp[rit[R]][curr].se};
curr=pp[rit[R]][curr].fi;
}
PP[A[X[it]]]={B[X[it]],X[it]};
R=A[X[it]];
st.erase(it);
break;
}
}
if (rit[R]==-1) add(R);
}
RR[x]=R;
//cout<<"debug: "<<x<<" "<<R<<endl;
}
//rep(x,0,n) cout<<x<<" "<<PP[x].fi<<" "<<PP[x].se<<endl;
rep(x,0,q){
int grp=0;
if (x){
rep(i,0,4) if (s[k*5+(x-1)*4+i]=='1') grp+=1<<i;
}
grp=LL[grp];
int curr=T[x];
while (curr!=RR[grp]){
PP[curr]={pp[rit[RR[grp]]][curr].fi,pp[rit[RR[grp]]][curr].se};
curr=pp[rit[RR[grp]]][curr].fi;
}
vector<signed> stk;
curr=T[x];
while (curr){
stk.pub(PP[curr].se);
curr=PP[curr].fi;
}
reverse(all(stk));
//for (auto it:stk) cout<<it<<" "; cout<<endl;
answer(stk);
}
}
