#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});
}
}
}
for(int i=1;i<N;i++){
for(int j=0;j<15;j++){
if(edge[i]&(1<<j)){
s+='1';
}
else{
s+='0';
}
}
}
cout<<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 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;
int len=s.size();
vector<pair<int,int>>adj[N];
for(int i=0;i<len/15;i++){
int ind=0;
for(int j=0;j<15;j++){
if(s[i*15+j]=='1'){
ind+=(1<<j);
}
}
adj[A[ind]].pb({B[ind],ind});
adj[B[ind]].pb({A[ind],ind});
}
vector<bool>used(N,0);
queue<int>q;
q.push(0);
used[0]=true;
while(!q.empty()){
int x=q.front();
q.pop();
for(auto [y,e]:adj[x]){
if(!used[y]){
used[y]=true;
from[y]=x;
edge[y]=e;
q.push(y);
}
}
}
for(int i=0;i<Q;i++){
int cur=T[i];
vector<int>path;
while(cur>0){
path.pb(edge[cur]);
cur=from[cur];
}
answer(path);
}
return;
}
