#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
static const long mxN = 3e2 + 7;
static const ll inf = 4e18 + 7;
static vector<int> ans[10];
static ll mn[mxN][mxN], cost[mxN][10];
void Anna(int n, int m, int a[], int b[], ll c[], int q, int s[], int t[], int k, int u[])
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
mn[i][j] = inf;
mn[i][i] = 0;
}
for (int i = 0; i < m; i++)
mn[a[i]][b[i]] = c[i];
for (int i = 0; i < k; i++)
mn[a[u[i]]][b[u[i]]] = inf;
// Floyd tim min dis
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mn[i][j] = min(mn[i][j], mn[i][k] + mn[k][j]);
// cost[i][j] truy van s[i] -> t[i] di qua canh u[j]
for (int i = 0; i < q; i++)
{
for (int j = 0; j < k; j++)
cost[i][j] = mn[s[i]][a[u[j]]] + mn[b[u[j]]][t[i]];
cost[i][k] = mn[s[i]][t[i]];
ans[0].push_back(i);
}
vector<ii> mem;
for (int i = 1; i <= k; i++)
{
ll tmp = 0;
if (i < k)
tmp = c[u[i]];
for (int j = 0; j < i; j++)
{
vector<int> rem;
for (int v : ans[j])
{
if (cost[v][j] + c[u[j]] < cost[v][i] + tmp)
rem.push_back(v);
else
ans[i].push_back(v);
}
mem.push_back({ans[j].size(), rem.size()});
ans[j] = rem;
}
}
reverse(mem.begin(), mem.end());
ll mask = 0;
for (ii i : mem)
mask = mask * (i.fi + 1) + i.se;
while (mask)
{
Tap(mask & 1);
mask /= 2;
}
}
#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
static const long mxN = 3e2 + 7;
static const ll inf = 4e18 + 7;
static ll mn[mxN][mxN], cost[mxN][mxN], c[mxN];
static vector<ii> w[mxN];
static vector<int> ans[10];
static int trace[mxN][mxN], a[mxN], b[mxN], edge[100];
void Dij(int n, int stt)
{
for (int i = 0; i < n; i++)
{
mn[stt][i] = inf;
trace[stt][i] = -1;
}
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, stt});
mn[stt][stt] = 0;
while (pq.size())
{
ii j = pq.top();
pq.pop();
if (j.fi != mn[stt][j.se])
continue;
for (ii i : w[j.se])
{
if (mn[stt][i.fi] > j.fi + c[i.se])
{
mn[stt][i.fi] = j.fi + c[i.se];
trace[stt][i.fi] = i.se;
pq.push({mn[stt][i.fi], i.fi});
}
}
}
// cout << stt << '\n';
// for (int i = 0; i < n; i++)
// cout << trace[stt][i] << " ";
// cout << '\n';
}
void Trace(int u, int v)
{
vector<int> ans;
while (v != u)
{
break;
ans.push_back(trace[u][v]);
//cout << u << " " << v << " " << trace[u][v] << '\n';
v = a[trace[u][v]];
}
reverse(ans.begin(), ans.end());
for (int i : ans)
Answer(i);
}
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[])
{
for (int i = 0; i < m; i++)
{
a[i] = A[i];
b[i] = B[i];
c[i] = C[i];
if (c[i] != -1)
w[a[i]].push_back({b[i], i});
}
for (int i = 0; i < n; i++)
Dij(n, i);
// cost[i][j] truy van s[i] -> t[i] di qua canh u[j]
for (int i = 0; i < q; i++)
{
for (int j = 0; j < k; j++)
cost[i][j] = min(inf, mn[s[i]][a[u[j]]] + mn[b[u[j]]][t[i]]);
cost[i][k] = mn[s[i]][t[i]];
ans[0].push_back(i);
}
ll mask = 0;
for (int i = l - 1; i >= 0; i--)
mask = mask * 2 + x[i];
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < i; j++)
{
sort(ans[j].begin(), ans[j].end(), [&](int u, int v)
{
return (cost[u][j] - cost[u][i]) < (cost[v][j] - cost[v][i]);
});
int rem = mask % (ans[j].size() + 1);
mask /= (ans[j].size() + 1);
while (ans[j].size() > rem)
{
ans[i].push_back(ans[j].back());
ans[j].pop_back();
}
}
}
//cout << '\n';
for (int i = 0; i <= k; i++)
{
for (int j : ans[i])
edge[j] = i;
}
for (int i = 0; i < q; i++)
{
// s[i], t[i];
//cout << i << " " << edge[i] << '\n';
if (edge[i] == k)
Trace(s[i], t[i]);
else
{
edge[i] = u[edge[i]];
Trace(s[i], a[edge[i]]);
Answer(edge[i]);
Trace(b[edge[i]], t[i]);
}
Answer(-1);
}
}
