#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 pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
namespace{
const int MAXN = 10 * 1000 + 17;
const int MAXM = 20 * 1000 + 17;
const int MAXK = 300 + 17;
const int MAXQ = 16;
const int B1 = 4;
const int B2 = 14;
const ll INF = ll(1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
ll cena[MAXM];
vector<pii> graf[MAXN];
pii poprz[MAXN];
ll odl[MAXN];
bool jest[MAXN];
int gora[MAXQ + 1];
bool znikniety[MAXM];
priority_queue<pair<ll, int>> pq;
int n;
int jaki[MAXM];
int roz[MAXQ + 1];
void djikstra (int s) {
for (int i = 0; i < n; i ++) {
odl[i] = INF;
}
odl[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
//cout << v << ":\n";
int v = pq.top().nd;
ll d = -pq.top().st;
pq.pop();
if (d > odl[v]) {
continue;
}
for (auto x : graf[v]) {
if (odl[v] + cena[x.nd] < odl[x.st]) {
odl[x.st] = odl[v] + cena[x.nd];
poprz[x.st] = {v, x.nd};
pq.push({-odl[x.st], x.st});
}
}
}
}
}
string konwertuj (int x) {
string s = "";
for (int i = 0; i < B1; i ++) {
if ((1 << i) & x) {
s += "1";
} else {
s += "0";
}
}
return s;
}
string konwertuj2 (int x) {
string s = "";
for (int i = 0; i < B2; i ++) {
if ((1 << i) & x) {
s += "1";
} else {
s += "0";
}
}
return s;
}
string aoi(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<ll> C, vector<int> T, vector<int> X) {
string s = "";
n = N;
for (int i = 0; i < M; i ++) {
cena[i] = C[i];
graf[A[i]].pb({B[i], i});
graf[B[i]].pb({A[i], i});
}
for (int i = 0; i < K; i ++) {
znikniety[X[i]] = 1;
}
djikstra(0);
int cnt = 0;
for (int i = 0; i < Q; i ++) {
cnt ++;
int v = T[i];
while (v != 0) {
if (jest[v]) {
gora[cnt] = v;
break;
}
jest[v] = 1;
if (znikniety[poprz[v].nd]) {
jaki[poprz[v].nd] = cnt;
roz[cnt] ++;
}
v = poprz[v].st;
}
}
int min1 = 1, min2 = 2;
if (Q == 16) {
if (roz[min2] < roz[min1]) {
swap(min1, min2);
}
for (int i = 3; i <= Q; i ++) {
if (roz[i] < roz[min1]) {
swap(min1, min2);
min1 = i;
} else if (roz[i] < roz[min2]) {
min2 = i;
}
}
}
for (int i = 0; i < K; i ++) {
//cout << X[i] << ": " << jaki[X[i]] << "\n";
}
string s2 = "";
if (Q == 16) {
if (min1 > min2) {
swap(min1, min2);
}
for (int i = 0; i < K; i ++) {
if (jaki[X[i]] == min1 || jaki[X[i]] == min2) {
s += konwertuj(min1);
if (jaki[X[i]] == min1) {
s2 += "0";
} else {
s2 += "1";
}
} else {
if (jaki[X[i]] > min2) {
s += konwertuj(jaki[X[i]] - 1);
} else {
s += konwertuj(jaki[X[i]]);
}
}
}
} else {
for (int i = 0; i < K; i ++) {
s += konwertuj(jaki[X[i]]);
}
}
for (int i = 1; i <= Q; i ++) {
s += konwertuj2(gora[i]);
//cout << i << ": " << gora[i] << "\n";
}
if (Q == 16) {
s += konwertuj(min1 - 1);
s += konwertuj(min2 - 1);
s += s2;
}
//cout << s << "\n";
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 pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
namespace {
const int MAXN = 10 * 1000 + 17;
const int MAXM = 20 * 1000 + 17;
const int MAXK = 300 + 17;
const int MAXQ = 16;
const int B1 = 4;
const int B2 = 14;
const ll INF = ll(1000 * 1000 * 1000) * ll(1000 * 1000 * 1000);
ll cena[MAXM];
vector<pii> graf[MAXN];
int gora[MAXQ + 1];
int jaki[MAXM];
pii poprz[MAXN];
pii poprz2[MAXN];
ll odl[MAXN];
bool byl[MAXQ + 1];
int zap[MAXQ];
priority_queue<pair<ll, int>> pq;
vector<int> wyn;
int n;
void djikstra (int s, int ind) {
for (int i = 0; i < n; i ++) {
odl[i] = INF;
}
odl[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
//cout << v << ":\n";
int v = pq.top().nd;
ll d = -pq.top().st;
pq.pop();
if (d > odl[v]) {
continue;
}
for (auto x : graf[v]) {
if (odl[v] + cena[x.nd] < odl[x.st]) {
odl[x.st] = odl[v] + cena[x.nd];
poprz2[x.st] = {v, x.nd};
//cout << x.st << " " << v << "\n";
pq.push({-odl[x.st], x.st});
}
}
}
int v = zap[ind];
//cout << "zap: " << v << "\n";
while (v != s) {
poprz[v] = poprz2[v];
v = poprz2[v].st;
}
//cout << s << ": ";
for (int i = 0; i < n; i ++) {
//cout << odl[i] << " ";
}
//cout << "\n";
for (int i = 0; i < n; i ++) {
//cout << poprz[i].st << " " << poprz[i].nd << "\n";
}
}
}
void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<ll> C, vector<int> T, vector<int> X, string s){
n = N;
for (int i = 0; i < M; i ++) {
cena[i] = C[i];
graf[A[i]].pb({B[i], i});
graf[B[i]].pb({A[i], i});
}
for (int i = 0; i < K * B1; i += B1) {
int x = 0;
for (int j = 0; j < B1; j ++) {
if (s[i + j] == '1') {
x += (1 << j);
}
}
jaki[X[i/B1]] = x;
}
for (int i = 0; i < Q * B2; i += B2) {
int x = 0;
for (int j = 0; j < B2; j ++) {
if (s[K * B1 + i + j] == '1') {
x += (1 << j);
}
}
gora[i/B2 + 1] = x;
}
if (Q == 16) {
int min1 = 0;
for (int i = 0; i < B1; i ++) {
if (s[K * B1 + Q * B2 + i] == '1') {
min1 += (1 << i);
}
}
min1 ++;
int min2 = 0;
for (int i = 0; i < B1; i ++) {
if (s[K * B1 + Q * B2 + 4 + i] == '1') {
min2 += (1 << i);
}
}
min2 ++;
for (int i = 0; i < K; i ++) {
if (jaki[X[i]] >= min2) {
jaki[X[i]] ++;
}
}
int r = 0;
for (int i = 0; i < K; i ++) {
if (jaki[X[i]] == min1) {
if (s[K * B1 + Q * B2 + 8 + r] == '1') {
jaki[X[i]] = min2;
} else {
jaki[X[i]] = min1;
}
r ++;
}
}
}
for (int i = 0; i < K; i ++) {
//cout << X[i] << ": " << jaki[X[i]] << "\n";
}
for (int i = 1; i <= Q; i ++) {
//cout << i << ": " << gora[i] << "\n";
}
for (int i = 1; i <= Q; i ++) {
zap[i - 1] = T[i - 1];
for (int j = 0; j < K; j ++) {
if (jaki[X[j]] != i) {
cena[X[j]] = INF;
} else {
cena[X[j]] = 0;
}
}
djikstra(gora[i], i - 1);
}
for (int i = 0; i < Q; i ++) {
int v = T[i];
while (v != 0) {
wyn.pb(poprz[v].nd);
v = poprz[v].st;
}
reverse(wyn.begin(), wyn.end());
//cout << T[i] << ": ";
for (auto x : wyn) {
//cout << x << " ";
}
//cout << "\n";
answer(wyn);
wyn.clear();
}
}
