/*************************************
* author: marvinthang *
* created: 21.03.2024 16:27:06 *
*************************************/
#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i-- > 0; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
// end of template
namespace {
template <class A, class B> bool minimize(A &a, B b) { return a > b ? a = b, true : false; }
const long long INF = 1e18;
}
string aoi(int N, int M, int Q, int K, vector <int> A, vector <int> B, vector <long long> C, vector <int> T, vector <int> X) {
vector <vector <int>> adj(N);
REP(i, M) {
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
}
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
vector <long long> dist(N, INF);
vector <int> par(N, -1);
pq.emplace(dist[0] = 0, 0);
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != dist[u]) continue;
for (int i: adj[u]) {
int v = A[i] ^ B[i] ^ u;
if (minimize(dist[v], du + C[i])) {
pq.emplace(dist[v], v);
par[v] = i;
}
}
}
vector <int> lost_roads(M, -1), in_query(N, -1);
REP(i, K) lost_roads[X[i]] = i;
REP(i, Q) in_query[T[i]] = i;
REP(i, N) adj[i].clear();
FOR(i, 1, N) adj[A[par[i]] ^ B[par[i]] ^ i].push_back(par[i]);
vector <int> nodes(K, -1);
vector <int> pid(Q, -1);
auto dfs = [&] (auto &&self, int u) -> int {
vector <int> child;
for (int i: adj[u]) {
int v = self(self, A[i] ^ B[i] ^ u);
if (v == -1) continue;
child.push_back(v);
if (lost_roads[i] != -1) nodes[lost_roads[i]] = v;
}
if ((int) child.size() >= 2 && in_query[u] == -1) {
in_query[u] = pid.size();
pid.push_back(-1);
}
if (in_query[u] != -1) {
for (int v: child) pid[v] = in_query[u];
return in_query[u];
}
return child.empty() ? -1 : child[0];
};
dfs(dfs, 0);
string res;
int sz = pid.size();
int lg = __lg(sz) + 1;
vector <bool> is_leaf(sz, true);
REP(i, sz) if (pid[i] != -1) is_leaf[pid[i]] = false;
if (Q == 1) is_leaf[0] = false;
vector <int> id(sz, -1);
int cl = 0;
REP(i, sz) if (!is_leaf[i]) id[i] = cl++;
int lg2 = __lg(cl) + 1;
REP(i, Q) res += char('0' + is_leaf[i]);
REP(i, sz) {
if (pid[i] == -1) pid[i] = cl;
else pid[i] = id[pid[i]];
REP(j, lg2) res += char('0' + BIT(pid[i], j));
}
REP(i, K) {
if (nodes[i] == -1) nodes[i] = sz;
REP(j, lg) res += char('0' + BIT(nodes[i], j));
}
return res;
}
/*************************************
* author: marvinthang *
* created: 21.03.2024 16:32:33 *
*************************************/
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define REPD(i, n) for (int i = (n); i-- > 0; )
#define FOR(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); --i >= _a; )
#define FORE(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORDE(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
#include "debug.h"
#else
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define DB(...) 23
#define db(...) 23
#define debug(...) 23
#endif
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
// end of template
namespace {
template <class A, class B> bool minimize(A &a, B b) { return a > b ? a = b, true : false; }
const long long INF = 1e18;
}
void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B, vector<long long> C, vector<int> T, vector<int> X, string s) {
vector <vector <int>> adj(N);
REP(i, M) {
adj[A[i]].push_back(i);
adj[B[i]].push_back(i);
}
int t = 0;
vector <bool> is_leaf(Q, true);
REP(i, Q) if (s[t++] == '0') is_leaf[i] = false;
int num_leaf = count(ALL(is_leaf), true);
int lg = 0, lg2 = -1, sz = 0;
while (lg2 == -1) {
++lg;
int x = (int) s.size() - t - K * lg;
FORE(i, 1, lg) if (x % i == 0) {
int v = x / i;
if (num_leaf <= v && v < MASK(lg) && __lg(v - num_leaf) + 1 == i) {
lg2 = i;
sz = v;
break;
}
}
}
vector <int> nd;
REP(i, sz) if (i >= Q || !is_leaf[i]) nd.push_back(i);
nd.push_back(-1);
vector <int> par(sz), nodes(K);
REP(i, sz) {
int x = 0;
REP(j, lg2) if (s[t++] == '1') x |= MASK(j);
par[i] = nd[x];
}
REP(i, K) REP(j, lg) if (s[t++] == '1') nodes[i] |= MASK(j);
vector <vector <int>> child(sz);
vector <int> tmask(sz + 1);
int rt = -1;
REP(i, sz) {
if (par[i] == -1) rt = i;
else child[par[i]].push_back(i);
}
auto dfs = [&] (auto &&self, int u) -> void {
if (u < Q) tmask[u] = MASK(u);
for (int v: child[u]) {
self(self, v);
tmask[u] |= tmask[v];
}
};
dfs(dfs, rt);
REP(t, Q) {
REP(i, K) C[X[i]] = BIT(tmask[nodes[i]], t) ? 0 : INF;
priority_queue <pair <long long, int>, vector <pair <long long, int>>, greater <pair <long long, int>>> pq;
vector <long long> dist(N, INF);
vector <int> trace(N, -1);
pq.emplace(dist[0] = 0, 0);
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != dist[u]) continue;
for (int i: adj[u]) {
int v = A[i] ^ B[i] ^ u;
if (minimize(dist[v], du + C[i])) {
pq.emplace(dist[v], v);
trace[v] = i;
}
}
}
int u = T[t];
vector <int> res;
while (u) {
int i = trace[u];
res.push_back(i);
u = A[i] ^ B[i] ^ u;
}
reverse(res.begin(), res.end());
answer(res);
}
}
