#include "Annalib.h"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <utility>
#include <vector>
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll inf = numeric_limits<ll>::max() / 3;
vector use(M, true);
for (int i = 0; i < K; ++i) {
use[U[i]] = false;
}
vector d(N, vector(N, inf));
for (int i = 0; i < N; ++i) {
d[i][i] = 0;
}
for (int i = 0; i < M; ++i) {
if (use[i]) {
d[A[i]][B[i]] = C[i];
}
}
for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
map<int, vector<int>> g = {};
{
vector<int> v(Q);
iota(begin(v), end(v), 0);
g.emplace(-1, move(v));
}
ull send = 0, coeff = 1;
for (int k = 0; k < K; ++k) {
map<int, vector<int>> g2 = {};
for (const auto& [j, v] : g) {
if (j == -1) {
for (const int i : v) {
if (d[S[i]][T[i]] - d[S[i]][A[U[k]]] - d[B[U[k]]][T[i]] <= C[U[k]]) {
send += coeff;
g2[j].push_back(i);
} else {
g2[k].push_back(i);
}
}
} else {
for (const int i : v) {
if (d[B[U[j]]][T[i]] - d[B[U[k]]][T[i]] <= C[U[k]] - C[U[j]]) {
send += coeff;
g2[j].push_back(i);
} else {
g2[k].push_back(i);
}
}
}
coeff *= v.size() + 1;
}
g = move(g2);
}
for (int i = 0; i < 64; ++i) {
Tap(send >> i & 1);
}
}
#include "Brunolib.h"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <utility>
#include <vector>
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll inf = numeric_limits<ll>::max() / 3;
vector use(M, true);
for (int i = 0; i < K; ++i) {
use[U[i]] = false;
}
vector d(N, vector(N, inf));
vector adj(N, vector(N, -1));
for (int i = 0; i < N; ++i) {
d[i][i] = 0;
}
for (int i = 0; i < M; ++i) {
if (use[i]) {
d[A[i]][B[i]] = C[i];
adj[A[i]][B[i]] = i;
}
}
for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
vector rev(N, vector(N, -1));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
if (const int e = adj[k][j]; e != -1 and d[i][j] == d[i][A[e]] + C[e] + d[B[e]][j]) {
rev[i][j] = e;
}
}
}
}
ull receive = 0;
for (int i = 0; i < L; ++i) {
receive |= (ull)X[i] << i;
}
map<int, vector<int>> g = {};
{
vector<int> v(Q);
iota(begin(v), end(v), 0);
g.emplace(-1, move(v));
}
for (int k = 0; k < K; ++k) {
map<int, vector<int>> g2 = {};
for (const auto& [j, v] : g) {
vector<pair<ll, int>> v2;
if (j == -1) {
for (const int i : v) {
v2.emplace_back(d[S[i]][T[i]] - d[S[i]][A[U[k]]] - d[B[U[k]]][T[i]], i);
}
} else {
for (const int i : v) {
v2.emplace_back(d[B[U[j]]][T[i]] - d[B[U[k]]][T[i]], i);
}
}
sort(begin(v2), end(v2));
const int n = (int)v.size();
const int m = receive % (n + 1);
receive /= n + 1;
for (int i = 0; i < m; ++i) {
g2[j].push_back(v2[i].second);
}
for (int i = m; i < n; ++i) {
g2[k].push_back(v2[i].second);
}
}
g = move(g2);
}
vector<int> type(Q);
for (const auto& [j, v] : g) {
for (const int i : v) {
type[i] = j;
}
}
for (int i = 0; i < Q; ++i) {
vector<int> ans;
const auto add = [&](const int u, int v) {
while (v != u) {
const int e = rev[u][v];
ans.push_back(e);
v = A[e];
}
};
if (const int j = type[i]; j == -1) {
add(S[i], T[i]);
} else {
add(B[U[j]], T[i]);
ans.push_back(U[j]);
add(S[i], A[U[j]]);
}
reverse(begin(ans), end(ans));
for (const int j : ans) {
Answer(j);
}
Answer(-1);
}
}
