#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
string aoi(signed n, signed m, signed q, signed k, vector<signed> A, vector<signed> B, vector<int> w, vector<signed> t, vector<signed> x){
vector<vector<pii> > graph(n);
for (int i=0; i<m; ++i){
graph[A[i]].pb(mp(B[i], i));
graph[B[i]].pb(mp(A[i], i));
}
vector<int> forgot(m, -1), l(k, q), r(q, k);
for (int i=0; i<k; ++i)forgot[x[i]]=i;
priority_queue<pair<pii, pii>, vector<pair<pii, pii> >, greater<pair<pii, pii> > > pq;
vector<pii> par(n, mp(-1, -1));
pq.push(mp(mp(0, 0), mp(0, -1)));
while (pq.size()){
int d=pq.top().fi.fi, node=pq.top().fi.se, p=pq.top().se.fi, pe=pq.top().se.se;
pq.pop();
if (par[node].fi!=-1)continue;
par[node]=mp(p, pe);
for (auto num:graph[node])pq.push(mp(mp(d+w[num.se], num.fi), mp(node, forgot[num.se])));
}
for (int i=0; i<q; ++i)for (int c=t[i]; c; c=par[c].fi)if (par[c].se!=-1){
if (l[par[c].se]==q)l[par[c].se]=i;
else{
r[par[c].se]=i;
break;
}
}
string s="";
for (int i=0; i<q; ++i)for (int b=0; b<9; ++b)s+=to_string(!!(r[i]&(1<<b)));
for (int i=0; i<k; i+=2){
if (i==k-1)for (int b=0; b<9; ++b)s+=to_string(!!(l[i]&(1<<b)));
else for (int b=0; b<9; ++b)s+=to_string(!!((l[i]+l[i+1]*17)&(1<<b)));
}
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
void bitaro(signed n, signed m, signed q, signed k, vector<signed> A, vector<signed> B, vector<int> w, vector<signed> t, vector<signed> x, string s){
int p=0;
vector<vector<pii> > graph(n);
for (int i=0; i<m; ++i){
graph[A[i]].pb(mp(B[i], i));
graph[B[i]].pb(mp(A[i], i));
}
vector<int> forgot(m, -1), l(k, q), r(q, k);
for (int i=0; i<k; ++i)forgot[X[i]]=i;
for (int i=0; i<q; ++i)for (int b=0; b<9; ++b)r[i]+=(1<<b)*(s[p]-'0'), ++p;
for (int i=0; i<k; i+=2){
int res=0;
for (int b=0; b<9; ++b)res+=(1<<b)*(s[p]-'0'), ++p;
l[i]=res%17;
if (i!=k-1)r[i]=res/17;
}
vector<pii> fpar(n, mp(-1, -1));
fpar[0]=mp(0, -1);
for (int ooga=0; ooga<q; ++ooga){
vector<bool> in(k, 0);
if (r[ooga]!=k){
in[r[ooga]]=1;
for (int c=A[x[r[ooga]]]; c; c=fpar[c].fi)if (forgot[fpar[c].se]!=-1)in[forgot[fpar[c].se]]=1;
}
for (int i=0; i<k; ++i)if (l[i]==ooga)in[i]=1;
for (int i=0; i<k; ++i)w[x[i]]=(in[i]?0:LLONG_MAX/2);
vector<pii> par(n, mp(-1, -1));
priority_queue<pair<pii, pii>, vector<pair<pii, pii> >, greater<pair<pii, pii> > > pq;
pq.push(mp(mp(0, 0), mp(0, -1)));
while (pq.size()){
int d=pq.top().fi.fi, node=pq.top().fi.se, p=pq.top().se.fi, pe=pq.top().se.se;
pq.pop();
if (par[node].fi!=-1)continue;
par[node]=mp(p, pe);
for (auto num:graph[node])pq.push(mp(mp(d+w[num.se], num.fi), mp(node, num.se)));
}
vector<signed> res;
for (int c=t[ooga]; c; c=par[c].fi)fpar[c]=par[c], res.pb(par[c].se);
reverse(res.begin(), res.end());
answer(res);
}
}
