#include "Aoi.h"
#include <bits/stdc++.h>
#define ent '\n'
#define int long long
using namespace std;
namespace {
const int maxn = 20020;
int n, m, q, k;
vector<array<int, 3> > g[maxn];
vector<pair<int, int> > e[maxn];
int pr[maxn], reb[maxn], d[maxn];
int pos[maxn], lol[maxn], tp[maxn];
vector<int> ord;
int tin[maxn], tout[maxn], is[maxn], timer;
int up[22][maxn], depth[maxn];
void dfs(int v) {
for(int i = 1; i < 20; i++) {
up[i][v] = up[i - 1][up[i - 1][v]];
}
tin[v] = ++timer;
if(is[v]) {
ord.push_back(tp[v]);
}
for(auto [to, id]: e[v]) {
up[0][to] = v;
depth[to] = depth[v] + 1;
dfs(to);
lol[id] = 1;
}
tout[v] = timer;
}
int dp[maxn];
bool check(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int get(int u, int v) {
if(check(u, v)) return u;
if(check(v, u)) return v;
for(int i = 19; i >= 0; i--) {
if(up[i][u] != 0 && !check(up[i][u], v)) {
u = up[i][u];
}
}
return u;
}
int p[maxn], cur[maxn], sz[maxn], L[maxn], R[maxn], nv;
int get(int x) {
if(p[x] == x) return x;
return p[x] = get(p[x]);
}
void merge(int x, int y) {
x = get(x), y = get(y);
if(x == y) return;
cur[y] = nv;
L[nv] = x, R[nv] = y;
sz[nv] = sz[L[nv]] + sz[R[nv]];
nv++;
p[x] = y;
}
int ver[16][16], pl;
int get_num(int v, int left) {
if(L[v] < 0) return 0;
ver[left][left + sz[v] - 1] = pl;
pl++;
int cur = 0;
for(int i = 1; i < sz[L[v]]; i++) {
cur += dp[i] * dp[sz[v] - i];
}
cur += get_num(L[v], left) + dp[sz[L[v]]] * get_num(R[v], left + sz[L[v]]);
return cur;
}
} // namespace
string aoi(int32_t N, int32_t M, int32_t Q, int32_t K, vector<int32_t> A,
vector<int32_t> B, vector<long long> C,
vector<int32_t> T, vector<int32_t> X) {
n = N, m = M, q = Q, k = K;
nv = q;
for(int i = 0; i < q; i++) {
p[i] = i;
sz[i] = 1;
L[i] = R[i] = -1;
}
dp[1] = 1;
for(int i = 2; i <= q; i++) {
for(int x = 1; x < i; x++) {
dp[i] += dp[x] * dp[i - x];
}
}
for(int i = 0; i < m; i++) {
pos[i] = -1;
g[A[i]].push_back({B[i], C[i], i});
g[B[i]].push_back({A[i], C[i], i});
}
for(int i = 0; i < q; i++) {
is[T[i]] = 1;
tp[T[i]] = i;
}
for(int i = 0; i < k; i++) {
pos[X[i]] = i;
}
for(int i = 1; i < n; i++) {
d[i] = 1e18;
}
d[0] = 0;
set<pair<int, int> > s;
s.insert({0, 0});
while(!s.empty()) {
int v = s.begin()->second;
if(v != 0) {
e[pr[v]].push_back({v, reb[v]});
}
s.erase(s.begin());
for(auto [to, w, id]: g[v]) {
if(d[to] > d[v] + w) {
s.erase({d[to], to});
pr[to] = v, reb[to] = id;
d[to] = d[v] + w;
s.insert({d[to], to});
}
}
}
dfs(0);
string ans(24 + k * 5 + (int)ord.size() * 4, '0');
for(int i = 0; i < m; i++) {
if(tin[A[i]] > tin[B[i]]) {
swap(A[i], B[i]);
}
}
vector<pair<int, int>> t;
for(int i = 0; i + 1 < ord.size(); i++) {
t.push_back({depth[get(T[ord[i]], T[ord[i + 1]])], i});
}
for(auto [td, i] : t) {
merge(i, i + 1);
}
int num = get_num(nv - 1, 0);
for(int i = 0; i < 24; i++) {
if((num >> i) & 1) {
ans[i] = '1';
}
}
ver[15][0] = 31;
for(int i = 0; i < k; i++) {
int l = 15, r = 0;
if(lol[X[i]]) {
for(int j = 0; j < ord.size(); j++) {
if(check(B[X[i]], T[ord[j]])) {
if(l > r) l = j;
r = j;
}
}
}
int val = ver[l][r];
for(int j = 0; j < 5; j++) {
if((val >> j) & 1) {
ans[24 + i * 5 + j] = '1';
}
}
}
for(int i = 0; i < ord.size(); i++) {
for(int j = 0; j < 4; j++) {
if((ord[i] >> j) & 1) {
ans[k * 5 + i * 4 + j + 24] = '1';
}
}
}
return ans;
}
#undef int
#include "Bitaro.h"
#include <bits/stdc++.h>
#define ent '\n'
#define int long long
using namespace std;
namespace {
const int maxn = 20020;
int n, m, q, k;
vector<array<int, 3>> g[maxn];
int pr[maxn], reb[maxn], d[maxn];
int pos[maxn], need[maxn], dp[maxn];
int pl, L[maxn], R[maxn];
void get(int l, int r, int num) {
L[pl] = l, R[pl] = r;
pl++;
if(l == r) return;
for(int mid = l; mid <= r; mid++) {
if(dp[mid - l + 1] * dp[r - mid] > num) {
get(l, mid, num % dp[mid - l + 1]);
get(mid + 1, r, num / dp[mid - l + 1]);
return;
}
num -= dp[mid - l + 1] * dp[r - mid];
}
}
} // namespace
void bitaro(int32_t N, int32_t M, int32_t Q, int32_t K, std::vector<int32_t> A, std::vector<int32_t> B,
std::vector<long long> C, std::vector<int32_t> T, std::vector<int32_t> X,
std::string s) {
n = N, m = M, q = Q, k = K;
dp[1] = 1;
for(int i = 2; i <= q; i++) {
for(int j = 1; j < i; j++) {
dp[i] = dp[j] * dp[i - j];
}
}
for(int i = 0; i < m; i++) {
pos[i] = -1;
g[A[i]].push_back({B[i], C[i], i});
g[B[i]].push_back({A[i], C[i], i});
}
for(int i = 0; i < k; i++) {
pos[X[i]] = i;
}
vector<int> ord;
int tl = k * 5 + 24;
int num = 0;
for(int i = 0; i < 24; i++) {
if(s[i] == '1') {
num += (1 << i);
}
}
get(0, q - 1, num);
for(int i = 0; tl + i * 4 + 3 < s.size(); i++) {
int val = 0;
for(int j = 0; j < 4; j++) {
if(s[tl + i * 4 + j] == '1') {
val += (1 << j);
}
}
ord.push_back(val);
}
L[31] = 15;
for(int _ = 0; _ < q; _++) {
int st = T[_];
int ps = 0;
while(T[ord[ps]] != st) {
ps++;
}
for(int j = 0; j < k; j++) {
need[j] = 0;
}
for(int t = 0; t < k; t++) {
int ver = 0;
for(int j = 0; j < 5; j++) {
if(s[24 + t * 5 + j] == '1') {
ver += (1 << j);
}
}
if(L[ver] <= ps && ps <= R[ver]) {
need[t] = 1;
}
}
for(int i = 1; i < n; i++) {
d[i] = 1e18;
}
set<pair<int, int>> s;
s.insert({0, 0});
while(!s.empty()) {
int v = s.begin() -> second;
s.erase(s.begin());
for(auto [to, w, id] : g[v]) {
if(pos[id] >= 0) {
if(need[pos[id]]) {
w = 0;
}
else {
continue;
}
}
if(d[to] > d[v] + w) {
s.erase({d[to], to});
pr[to] = v, reb[to] = id;
d[to] = d[v] + w;
s.insert({d[to], to});
}
}
}
vector<int32_t> ans;
while(st > 0) {
ans.push_back(reb[st]);
st = pr[st];
}
reverse(ans.begin(), ans.end());
answer(ans);
}
}
#undef int
