#include "Aoi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pii pair<ll,ll>
#define vii vector<pair<ll,ll>>
#define vi vector<int>
#define pll pair<ll, ll>
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define count_bits(x) __builtin_popcountll((x))
const ll M = 1e9+7;
const ll INF = 1e9;
//mt19937 mt;void random_start(){mt.seed(chrono::time_poll_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll MAXK = 305;
const ll MAXN = 1e4 + 5;
const ll MAXM = 2e4 + 5;
vii graf[MAXN];
ll uzyta[MAXN];
struct d{
ll v;
ll odl;
ll c;
};
struct comp{
bool operator()(const d &d1, const d &d2){
if(d1.odl != d2.odl) return d1.odl > d2.odl;
return false;
}
};
ll doktorego[MAXM];
ll krawedzdoczep[16];
ll specj[MAXM];
ll used[MAXN];
string aoi(int N, int M, int Q, int K, vi A, vi B, vi C, vi T, vi X){
for(auto u : X){
specj[u] = 1;
}
for(ll i = 0; i < M; ++i){
graf[A[i]].push_back({B[i], i});
graf[B[i]].push_back({A[i], i});
}
for(ll i = 0; i < N; ++i){
uzyta[i] = -1;
}
priority_queue<d, vector<d>, comp> pq;
pq.push({0, 0, 0});
while(!pq.empty()){
auto e = pq.top();
pq.pop();
if(uzyta[e.v] != -1) continue;
uzyta[e.v] = e.c;
for(auto u : graf[e.v]){
if(uzyta[u.first] != -1) continue;
pq.push({u.first, e.odl + C[u.second], u.second});
}
}
for(ll i = 1; i <= Q; ++i){
ll v = T[i-1];
if(used[v] == 1){
ll tmp = v;
while(true){
if(tmp == 0){
krawedzdoczep[i] = -1;
break;
}
if(specj[uzyta[tmp]] == 1){
krawedzdoczep[i] = uzyta[tmp];
break;
}
ll d2 = A[uzyta[tmp]]; if(d2 == tmp) d2 = B[uzyta[tmp]]; tmp = d2;
}
continue;
}
while(true){
used[v] = 1;
ll drugi = A[uzyta[v]];
if(drugi == v) drugi = B[uzyta[v]];
if(specj[uzyta[v]] == 1){
doktorego[uzyta[v]] = i;
}
if(used[drugi] == 1){
ll tmp = drugi;
while(true){
if(tmp == 0){
krawedzdoczep[i] = -1;
break;
}
if(specj[uzyta[tmp]] == 1){
krawedzdoczep[i] = uzyta[tmp];
break;
}
ll d2 = A[uzyta[tmp]]; if(d2 == tmp) d2 = B[uzyta[tmp]]; tmp = d2;
}
break;
}
v = drugi;
}
}
ll cnt = 1;
string s = "";
for(ll i = 0; i < K; ++i){
ll kr = X[i];
for(ll j = 0; j < 5; ++j){
s += ((doktorego[kr] & (1 << j)) != 0 ? '1' : '0');
}
}
for(ll i = 2; i <= Q; ++i){
ll vl;
if(krawedzdoczep[i] == -1){
vl = 0;
}
else{
vl = doktorego[krawedzdoczep[i]];
}
for(ll j = 0; j < 4; ++j){
s += ((vl & (1 << j)) != 0 ? '1' : '0');
}
}
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pii pair<ll,ll>
#define vii vector<pair<ll,ll>>
#define vi vector<ll>
#define pll pair<ll, ll>
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define count_bits(x) __builtin_popcountll((x))
const ll M = 1e9+7;
const ll INF = 2e18;
//mt19937 mt;void random_start(){mt.seed(chrono::time_poll_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll MAXK = 305;
const ll MAXN = 1e4 + 5;
const ll MAXM = 2e4 + 5;
ll poprz[MAXN];
vii graf[MAXN];
vi ktore[MAXN];
ll pot2[6];
ll doktoregopodkoniec[17];
vi pomnie[17];
ll powrot[MAXN];
ll odl[MAXN];
ll tyl[MAXN];
struct d{
ll v;
ll o;
ll p;
};
struct comp{
bool operator()(const d &d1, const d &d2){
if(d1.o != d2.o) return d1.o > d2.o;
return false;
}
};
void Dijkstra(ll curr, const vi &C, const ll &N){
for(ll i = 0; i < N; ++i){
odl[i] = -1;
}
priority_queue<d, vector<d>, comp> pq;
pq.push({curr, 0, curr});
while(!pq.empty()){
auto u = pq.top();
pq.pop();
if(odl[u.v] != -1 or u.o > INF) continue;
odl[u.v] = u.o;
tyl[u.v] = u.p;
for(auto t : graf[u.v]){
pq.push({t.first, u.o + C[t.second], u.v});
}
}
return;
}
vi drugi[MAXN];
void R(ll ind, ll curr, const vi &A, const vi &B, const vi &C, const ll &N, const ll &M){
unordered_set<ll> aktywne;
for(auto u : ktore[ind]){
aktywne.insert(A[u]);
aktywne.insert(B[u]);
drugi[A[u]].push_back(B[u]);
drugi[B[u]].push_back(A[u]);
}
auto matching = [&](ll a, ll b) -> ll {
for(auto u : drugi[a]){
if(u != b) return u;
}
return -1;
};
while(aktywne.size() > 0 or curr == 0){
Dijkstra(curr, C, N);
ll mini = INF;
ll ind = -1;
for(auto u : aktywne){
if(odl[u] != -1 and odl[u] < mini){
mini = odl[u];
ind = u;
}
}
ll C = ind;
while(C != curr){
powrot[tyl[C]] = C;
C = tyl[C];
}
C = ind;
ll p = -1;
while(true){
aktywne.erase(C);
curr = C;
if(C == 0) break;
ll w = matching(C, p);
if(w != -1){
powrot[C] = w;
p = C;
C = w;
}
else{
break;
}
}
}
if(curr != 0){
Dijkstra(curr, C, N);
ll mini = INF;
ll ind = -1;
for(auto u : aktywne){
if(powrot[u] != -1 and odl[u] != -1 and odl[u] < mini){
mini = odl[u];
ind = u;
}
}
ll C = ind;
while(C != curr){
powrot[tyl[C]] = C;
C = tyl[C];
}
}
for(auto u : ktore[ind]){
drugi[A[u]].clear();
drugi[B[u]].clear();
}
return;
}
void bitaro(ll N, ll M, ll Q, ll K, vi A, vi B, vi C, vi T, vi X, string s){
pot2[0] = 1;
for(ll i = 1; i < 6; ++i){
pot2[i] = pot2[i-1] * 2;
}
for(ll i = 0; i < M; ++i){
graf[A[i]].push_back({B[i], i});
graf[B[i]].push_back({A[i], i});
}
for(ll i = 0; i < K; ++i){
C[X[i]] = INF;
}
ll it = 0;
for(ll i = 0; i < K; ++i){
ll vl = 0;
for(ll j = 0; j < 5; ++j){
vl += (s[it] - '0') * pot2[j];
++it;
}
if(vl == 0) continue;
ktore[vl].push_back(i);
}
for(ll i = 2; i <= Q; ++i){
ll vl = 0;
for(ll j = 0; j < 4; ++j){
vl += (s[it] - '0') * pot2[j];
++it;
}
doktoregopodkoniec[i] = vl;
}
doktoregopodkoniec[1] = 0;
for(ll i = 1; i <= Q; ++i){
pomnie[doktoregopodkoniec[i]].push_back(i);
}
for(ll i = 0; i < N; ++i){
powrot[i] = -1;
}
powrot[0] = 0;
queue<ll> que;
que.push(0);
while(!que.empty()){
ll x = que.front();
ll w = T[x-1];
que.pop();
if(powrot[w] == -1){
R(x, w, A, B, C, N, M);
}
for(auto u : pomnie[x]){
que.push(u);
}
}
for(ll i = 1; i <= Q; ++i){
vector<int> ans;
ll curr = T[i-1];
while(curr != 0){
ans.push_back(curr);
curr = powrot[curr];
}
ans.push_back(0);
reverse(all(ans));
answer(ans);
}
return;
}
