#include "Aoi.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

typedef long long ll;
typedef double lf;

using namespace std;

namespace
{
	const int MAXN = 2e4 + 10;

	int n, m, bel[MAXN], st[20];
	int num[MAXN];

	vector <pair <int, int>> e[MAXN];
	vector <ll> eval;
	ll dis[MAXN]; bool vis[MAXN];
	int pre[MAXN], pth[MAXN];
	struct Node
	{
		ll dis; int x;
		bool operator < (const Node &u) const { return dis == u.dis ? x < u.x : dis > u.dis; }
	};
	priority_queue <Node> q;
	inline void Dijkstra(int s)
	{
		dis[s] = 0, q.push(Node{dis[s], s});
		while (!q.empty())
		{
			int u = q.top().x; q.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (auto [v, w] : e[u])
				if (dis[v] > dis[u] + eval[w])
				{
					dis[v] = dis[u] + eval[w], pre[v] = u, pth[v] = w;
					q.push(Node{dis[v], v});
				}
		}
	}
}

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)
{
	n = N, m = M, eval = C;
	for (int i = 0; i < m; i++) e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i), bel[i] = Q, num[i] = -1;
	for (int i = 0; i < K; i++) num[X[i]] = i;
	for (int i = 0; i < n; i++) dis[i] = 1e18;
	Dijkstra(0);
	for (int i = 0; i < n; i++) vis[i] = 0;
	for (int i = 0; i < Q; i++)
	{
		int u = T[i];
		st[i] = K;
		while (u)
		{
			if (!vis[u]) bel[pth[u]] = i;
			else if (~num[pth[u]]) { st[i] = num[pth[u]]; break; }
			vis[u] = 1, u = pre[u];
		}
	}
	string ret;
	for (int i = 0; i + 1 < K; i += 2)
	{
		int cur = bel[X[i]] * 17 + bel[X[i + 1]];
		for (int j = 0; j < 9; j++)
			ret.push_back(cur & (1 << j) ? '1' : '0');
	}
	if (K & 1)
		for (int i = 0; i < 5; i++)
			ret.push_back(bel[X[K - 1]] & (1 << i) ? '1' : '0');
	for (int i = 1; i < Q; i++)
		for (int j = 0; j < 9; j++)
			ret.push_back(st[i] & (1 << j) ? '1' : '0');
	return ret;
}

#include "Bitaro.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

typedef long long ll;
typedef double lf;

using namespace std;

namespace
{
	const int MAXN = 2e4 + 10;

	int n, m, bel[MAXN];
	int num[MAXN], bck[MAXN], ed[MAXN];

	vector <pair <int, int>> e[MAXN];
	vector <ll> eval;
	ll dis[MAXN]; bool vis[MAXN];
	int pre[MAXN], pth[MAXN];
	struct Node
	{
		ll dis; int x;
		bool operator < (const Node &u) const { return dis == u.dis ? x < u.x : dis > u.dis; }
	};
	priority_queue <Node> q;
	inline void Dijkstra(int s)
	{
		dis[s] = 0, q.push(Node{dis[s], s});
		while (!q.empty())
		{
			int u = q.top().x; q.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (auto [v, w] : e[u])
				if (dis[v] > dis[u] + eval[w])
				{
					dis[v] = dis[u] + eval[w], pre[v] = u, pth[v] = w;
					q.push(Node{dis[v], v});
				}
		}
	}
}

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 ret)
{
	n = N, m = M, eval = C;
	for (int i = 0; i < m; i++) e[A[i]].emplace_back(B[i], i), e[B[i]].emplace_back(A[i], i), num[i] = -1;
	for (int i = 0; i < K; i++) num[X[i]] = i;

	int x = 0;
	for (int i = 0; i + 1 < K; i += 2)
	{
		ll cur = 0;
		for (int j = 0; j < 9; j++)
			cur += (ret[x + j] - '0') << j;
		x += 9;
		bel[X[i]] = cur / 17, bel[X[i + 1]] = cur % 17;
	}
	if (K & 1)
	{
		for (int j = 0; j < 5; j++)
			bel[X[K - 1]] += (ret[x + j] - '0') << j;
		x += 5;
	}
	
	vector <int> res;
	for (int i = 0; i < Q; i++)
	{
		for (int j = 0; j < K; j++)
			if (bel[X[j]] != i) eval[X[j]] = 1e18;
			else eval[X[j]] = 0;
		int s = 0;
		if (i)
		{
			for (int j = 0; j < 9; j++) s += (ret[x + j] - '0') << j;
			x += 9;
			if (s == K) s = 0;
			else if (bck[A[X[s]]] == B[X[s]]) s = A[X[s]];
			else s = B[X[s]];
		}
		for (int j = 0; j < n; j++) dis[j] = 1e18, vis[j] = pre[j] = pth[j] = 0;
		Dijkstra(s);
		int u = T[i];
		while (u != s && !bck[u]) bck[u] = pre[u], ed[u] = pth[u], u = pre[u];
		u = T[i], res.clear();
		while (u) res.push_back(ed[u]), u = bck[u];
		reverse(res.begin(), res.end());
		answer(res);
	}
}