#include "Aoi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const ll INF = 1e16+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace {
vector<pii> graph[10001];
ll costs[20001];
pii up_vert[10001];
int color[20001];
bool odw[10001];
bool is_special[20001];
int path_beg[17];
int path_end[17];
int color_cnt[17];
int special_ind[20001];
ll dist[10001];
int n,m,q,k;
int dead_group = 16;
string ans;
void add_int(int x, int s)
{
rep(i,s)
{
if(x & (1 << i)) ans += '1';
else ans += '0';
}
}
void dijkstra()
{
priority_queue<pair<ll,pair<int,pii>>,vector<pair<ll,pair<int,pii>>>,greater<pair<ll,pair<int,pii>>>> pq;
pq.push({0,{0,{-1,-1}}});
while(!pq.empty())
{
pair<ll,pair<int,pii>> t = pq.top();
pq.pop();
if(odw[t.ss.ff]) continue;
odw[t.ss.ff] = 1;
dist[t.ss.ff] = t.ff;
up_vert[t.ss.ff] = t.ss.ss;
forall(it,graph[t.ss.ff])
{
pq.push({t.ff+costs[it.ss],{it.ff,{t.ss.ff,it.ss}}});
}
}
}
void swap_groups(int a, int b)
{
if(a == dead_group) dead_group = b;
else if(b == dead_group) dead_group = a;
swap(path_beg[a],path_beg[b]);
rep(i,m)
{
if(color[i] == a) color[i] = b;
else if(color[i] == b) color[i] = a;
}
swap(color_cnt[a],color_cnt[b]);
}
}
// swap(T,X)
string aoi(int N, int M, int Q, int K, vi A, vi B, vl C, vi X, vi T)
{
n = N; m = M; q = Q; k = K;
sort(all(T));
rep(i,m)
{
costs[i] = C[i];
color[i] = 16;
graph[A[i]].pb({B[i],i});
graph[B[i]].pb({A[i],i});
}
rep(i,17) path_beg[i] = -1;
rep(i,17) path_end[i] = -1;
int cur = 0;
rep(i,k)
{
is_special[T[i]] = 1;
special_ind[T[i]] = cur++;
}
dijkstra();
rep(i,q)
{
int v = X[i];
while(v != 0)
{
if(is_special[up_vert[v].ss])
{
if(path_end[i] == -1) path_end[i] = up_vert[v].ss;
if(color[up_vert[v].ss] == 16) color[up_vert[v].ss] = i;
else
{
path_beg[i] = up_vert[v].ss;
break;
}
}
v = up_vert[v].ff;
}
}
rep(i,k) color_cnt[color[T[i]]]++;
pii best = {1e9,-1};
rep(i,17) best = min(best,{color_cnt[i],i});
if(best.ss != 16) swap_groups(best.ss,16);
best = {1e9,-1};
rep(i,16) best = min(best,{color_cnt[i],i});
if(best.ss != 0) swap_groups(best.ss,0);
rep(i,k) add_int(color[T[i]],4);
add_int(dead_group,5);
rep(i,k) if(color[T[i]] % 16 == 0)
{
add_int(color[T[i]] == 16,1);
}
rep(i,17) add_int((path_beg[i] != -1 ? special_ind[path_beg[i]] : 301),9);
rep(i,q) add_int((path_end[i] != -1 ? special_ind[path_end[i]] : 301),9);
return ans;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const ll INF = 1e16+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace {
vector<pii> graph[10001];
ll costs[20001];
int color[20001];
int path_beg[17];
pair<int,vi> root_path[10001];
int rel_end[20001];
bool was[17];
int n,m,q,k;
int dead_group = 16;
pii up_vert[10001];
ll dist[10001];
vi A,B;
string ans;
int cur_poz = 0;
int get_int(int s)
{
int x = 0;
rep(i,s) if(ans[cur_poz++] == '1') x += (1<<i);
return x;
}
void dijkstra(int x)
{
priority_queue<pair<ll,pair<int,pii>>,vector<pair<ll,pair<int,pii>>>,greater<pair<ll,pair<int,pii>>>> pq;
pq.push({0,{x,{-1,0}}});
rep(i,n) dist[i] = -1;
while(!pq.empty())
{
pair<ll,pair<int,pii>> t = pq.top();
pq.pop();
if(dist[t.ss.ff] != -1) continue;
dist[t.ss.ff] = t.ff;
up_vert[t.ss.ff] = t.ss.ss;
forall(it,graph[t.ss.ff])
{
pq.push({t.ff+costs[it.ss],{it.ff,{t.ss.ff,it.ss}}});
}
}
}
vi get_path(int v, int beg)
{
vi path;
while(v != beg && v != -1)
{
path.pb(up_vert[v].ss);
v = up_vert[v].ff;
}
return path;
}
void add_path(int beg, vi x)
{
forall(it,x) costs[it] = 0;
dijkstra(beg);
forall(it,x) costs[it] = INF;
forall(it,x)
{
if(up_vert[A[it]].ff == B[it]) rel_end[it] = A[it];
else rel_end[it] = B[it];
int v = rel_end[it];
root_path[v] = {beg,get_path(v,beg)};
}
}
}
//swap(T,X)
void bitaro(int N, int M, int Q, int K, vi A2, vi B2, vl C, vi X, vi T, string S)
{
A = A2;
B = B2;
ans = S;
n = N; m = M; q = Q; k = K;
sort(all(T));
rep(i,m)
{
costs[i] = C[i];
color[i] = 18;
graph[A[i]].pb({B[i],i});
graph[B[i]].pb({A[i],i});
rel_end[i] = -1;
}
int cur = 0;
rep(i,k)
{
costs[T[i]] = INF;
}
while(siz(T) != 302) T.pb(-1);
rep(i,k) color[T[i]] = get_int(4);
dead_group = get_int(5);
rep(i,m) if(color[i] == 18) color[i] = dead_group;
rep(i,k) if(color[T[i]] % 16 == 0)
{
if(get_int(1)) color[T[i]] = 16;
}
rep(i,17)
{
path_beg[i] = get_int(9);
if(path_beg[i] == 301) path_beg[i] = -1;
else path_beg[i] = T[path_beg[i]];
}
while(true)
{
int x = -1;
rep(j,17)
{
if(j == dead_group || was[j]) continue;
if(path_beg[j] == -1 || rel_end[path_beg[j]] != -1) x = j;
}
if(x == -1) break;
was[x] = 1;
vi path;
rep(i,k) if(color[T[i]] == x) path.pb(T[i]);
if(siz(path) == 0) continue;
add_path((path_beg[x] != -1 ? rel_end[path_beg[x]] : 0),path);
}
rep(i,q)
{
int p = get_int(9);
int beg = 0;
if(p != 301) beg = rel_end[T[p]];
int v = X[i];
dijkstra(beg);
vi ans = get_path(v,beg);
v = beg;
while(v != 0)
{
forall(it,root_path[v].ss) ans.pb(it);
v = root_path[v].ff;
}
reverse(all(ans));
answer(ans);
}
}
