#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 maxn=1e4+5;
int from[maxn],edge[maxn];
long long dist[maxn];
vector<tuple<int,ll,int>>g[maxn];
} // 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="";
fill(dist,dist+N,(ll)1e18);
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});
}
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});
}
}
}
vector<bool>used(M,false);
for(int i=0;i<Q;i++){
fill(all(used),false);
int cur=T[i];
while(cur>0){
used[edge[cur]]=true;
cur=from[cur];
}
for(int j=0;j<K;j++){
if(used[X[j]]==true){
s+='1';
}
else{
s+='0';
}
}
}
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 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;
int 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});
}
}
}
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<M;i++){
if(C[i]==-1) continue;
g[A[i]].pb({B[i],C[i],i});
g[B[i]].pb({A[i],C[i],i});
}
for(int i=0;i<Q;i++){
vector<bool>used(K,false);
for(int j=0;j<K;j++){
if(s[i*K+j]=='1'){
used[j]=true;
}
}
for(int j=0;j<K;j++){
if(used[j]==true){
g[A[X[j]]].pb({B[X[j]],1,X[j]});
g[B[X[j]]].pb({A[X[j]],1,X[j]});
}
}
dijkstra();
vector<int>path;
int cur=T[i];
while(cur!=0){
path.pb(edge[cur]);
cur=from[cur];
}
reverse(all(path));
answer(path);
for(int j=0;j<K;j++){
if(used[j]==true){
g[A[X[j]]].pop_back();
g[B[X[j]]].pop_back();
}
}
}
return;
}
