#include<bits/stdc++.h>
#include "Aoi.h"

using namespace std;

typedef int ll;
typedef long long lll;

const lll INF = 1'000'000'000'000'000'000, COL2 = 5;

struct DSU {
	vector<ll> p, sz;
	DSU(ll n) {
		p.resize(n);
		sz.resize(n, 1);
		for (ll i = 0; i < n; i++) {
			p[i] = i;
		}
	}
	ll get(ll x) {
		return (p[x] == x ? x : p[x] = get(p[x]));
	}
	void unite(ll a, ll b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return;
		}
		if (sz[a] < sz[b]) {
			swap(a, b);
		}
		p[b] = a;
		sz[a] += sz[b];
	}
};

ll merge(ll a, ll b, ll& lst, string& ans) {
	if (a == 0) {
		return b;
	}
	if (b == 0) {
		return a;
	}
	for (ll i = 0; i < COL2; i++) {
		ans.push_back('0' + ((a >> i) & 1));
	}
	for (ll i = 0; i < COL2; i++) {
		ans.push_back('0' + ((b >> i) & 1));
	}
	lst++;
	return lst;
}

ll dfs(ll v, vector<vector<pair<ll, lll>>>& arr, vector<ll>& isdel, vector<ll>& num, vector<ll>& snum, ll& lst, string& ans) {
	ll now = snum[v];
	for (auto[i, _] : arr[v]) {
		now = merge(now, dfs(i, arr, isdel, num, snum, lst, ans), lst, ans);
	}
	if (isdel[v] != -1) {
		num[isdel[v]] = now;
	}
	return now;
}

string aoi(ll n, ll m, ll q, ll k, vector<ll> a, vector<ll> b, vector<lll> c, vector<ll> t, vector<ll> x) {
	string ans;
	vector<lll> dist(n, INF);
	vector<vector<pair<ll, lll>>> arr(n);
	for (ll i = 0; i < m; i++) {
		arr[a[i]].emplace_back(b[i], c[i]);
		arr[b[i]].emplace_back(a[i], c[i]);
	}
	map<ll, ll> del;
	for (ll i = 0; i < k; i++) {
		del[x[i]] = i;
	}
	priority_queue<pair<ll, lll>, vector<pair<ll, lll>>, greater<pair<ll, lll>>> pq;
	pq.emplace(0, 0);
	dist[0] = 0;
	while (!pq.empty()) {
		auto[v, d] = pq.top();
		pq.pop();
		if (dist[v] != d) {
			continue;
		}
		for (auto[i, c] : arr[v]) {
			if (d + c < dist[i]) {
				dist[i] = d + c;
				pq.emplace(i, d + c);
			}
		}
	}
	DSU d(n);
	vector<tuple<ll, ll, lll, ll>> nr;
	vector<ll> isdel(n, -1);
	for (ll i = 0; i < n; i++) {
		arr[i].clear();
	}
	for (ll i = 0; i < m; i++) {
		if (d.get(a[i]) == d.get(b[i])) {
			continue;
		}
		if (dist[b[i]] == dist[a[i]] + c[i]) {
			nr.emplace_back(a[i], b[i], c[i], i);
			arr[a[i]].emplace_back(b[i], c[i]);
			if (del.find(i) != del.end()) {
				isdel[b[i]] = del[i];
			}
			d.unite(a[i], b[i]);
		}
		if (dist[a[i]] == dist[b[i]] + c[i]) {
			nr.emplace_back(b[i], a[i], c[i], i);
			arr[b[i]].emplace_back(a[i], c[i]);
			if (del.find(i) != del.end()) {
				isdel[a[i]] = del[i];
			}
			d.unite(a[i], b[i]);
		}
	}
	vector<ll> num(k, 0);
	vector<ll> snum(n, 0);
	ll lst = q;
	for (ll i = 0; i < q; i++) {
		snum[t[i]] = i + 1;
	}
	dfs(0, arr, isdel, num, snum, lst, ans);
	for (ll i = 0; i < k; i++) {
		for (ll j = 0; j < COL2; j++) {
			ans.push_back('0' + ((num[i] >> j) & 1));
		}
	}
	return ans;
}

#include<bits/stdc++.h>
#include "Bitaro.h"

using namespace std;

typedef int ll;
typedef long long lll;

const lll INF = 1'000'000'000'000'000'000, COL2 = 5;

void bitaro(ll n, ll m, ll q, ll k, vector<ll> a, vector<ll> b, vector<lll> c, vector<ll> t, vector<ll> x, string s) {
	set<ll> calc;
	calc.insert(0);
	for (auto i : x) {
		calc.insert(a[i]);
		calc.insert(b[i]);
		c[i] = INF + 1;
	}
	for (auto i : t) {
		calc.insert(i);
	}
	vector<vector<tuple<ll, lll, ll>>> arr(n);
	for (ll i = 0; i < m; i++) {
		arr[a[i]].emplace_back(b[i], c[i], i);
		arr[b[i]].emplace_back(a[i], c[i], i);
	}
	vector<vector<lll>> dist(n);
	vector<vector<ll>> p(n);
	for (auto i : calc) {
		dist[i].resize(n, INF);
		dist[i][i] = 0;
		p[i].resize(n, -1);
		priority_queue<pair<ll, lll>, vector<pair<ll, lll>>, greater<pair<ll, lll>>> pq;
		pq.emplace(i, 0);
		while (!pq.empty()) {
			auto[v, d] = pq.top();
			pq.pop();
			if (d != dist[i][v]) {
				continue;
			}
			for (auto[j, c, e] : arr[v]) {
				if (dist[i][j] > d + c) {
					dist[i][j] = d + c;
					p[i][j] = e;
					pq.emplace(j, d + c);
				}
			}
		}
	}
	vector<vector<ll>> nums(1 << COL2);
	for (ll i = 0; i < q; i++) {
		nums[i + 1].push_back(i);
	}
	vector<ll> all;
	while (!s.empty()) {
		ll now = 0;
		for (ll i = 0; i < COL2; i++) {
			now *= 2;
			now += s.back() - '0';
			s.pop_back();
		}
		all.push_back(now);
	}
	for (ll i = q + 1; i < q * 2; i++) {
		ll fir = all.back();
		all.pop_back();
		ll sec = all.back();
		all.pop_back();
		nums[i].resize(nums[fir].size() + nums[sec].size());
		merge(nums[fir].begin(), nums[fir].end(), nums[sec].begin(), nums[sec].end(), nums[i].begin());
	}
	vector<vector<ll>> qs(q);
	for (ll i = 0; i < k; i++) {
		ll now = all.back();
		all.pop_back();
		for (auto j : nums[now]) {
			qs[j].push_back(x[i]);
		}
	}
	for (ll i = 0; i < q; i++) {
		ll now = 0;
		multiset<ll> needs;
		needs.insert(-1);
		for (auto j : qs[i]) {
			needs.insert(j);
		}
		vector<ll> ans;
		while (now != t[i]) {
			lll md = INF;
			ll v = -228;
			bool bb;
			for (auto j : needs) {
				if (j == -1) {
					if (md > dist[now][t[i]]) {
						md = dist[now][t[i]];
						v = j;
					}
					continue;
				}
				if (md > dist[now][a[j]]) {
					md = dist[now][a[j]];
					v = j;
					bb = false;
				}
				if (md > dist[now][b[j]]) {
					md = dist[now][b[j]];
					v = j;
					bb = true;
				}
			}
			needs.erase(v);
			ll nv = (v == -1 ? t[i] : (bb ? b[v] : a[v]));
			vector<ll> ne;
			while (nv != now) {
				ne.push_back(p[now][nv]);
				nv = (a[p[now][nv]] == nv ? b[p[now][nv]] : a[p[now][nv]]);
			}
			reverse(ne.begin(), ne.end());
			for (auto j : ne) {
				ans.push_back(j);
			}
			if (v != -1) {
				ans.push_back(v);
			}
			now = (v == -1 ? t[i] : (bb ? a[v] : b[v]));
		}
		answer(ans);
	}
}