#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
string aoi(int N, int M, int Q, int K, vector<int> A,
vector<int> B, vector<ll> C,
vector<int> T, vector<int> X) {
sort(all(X));
vector<vector<tuple<int, ll, int>>> adj(N);
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], C[i], i);
adj[B[i]].emplace_back(A[i], C[i], i);
}
priority_queue<pair<ll, int>> pq;
vector<ll> dist(N, ll(1e18));
pq.emplace(-(dist[0] = 0), 0);
vector<int> par(N, -1);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop(); d *= -1;
if (d != dist[u]) continue;
for (auto [v, w, i] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
par[v] = i;
pq.emplace(-dist[v], v);
}
}
}
string ans = "";
for (int i = 0; i < Q; i++) {
int u = T[i];
set<int> used;
while (u != 0) {
used.insert(par[u]);
u ^= A[par[u]] ^ B[par[u]];
}
for (int j = 0; j < K; j++) {
ans += '0' + used.count(j);
}
}
return ans;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
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) {
sort(all(X));
int idx = 0;
for (int p = 0; p < Q; p++) {
int j = 0;
vector<vector<tuple<int, ll, int>>> adj(N);
for (int i = 0; i < M; i++) {
ll w = C[i];
if (j < K && X[j] == i) {
if (s[idx] == '0') w = ll(1e18);
else w = 0;
idx++, j++;
}
adj[A[i]].emplace_back(B[i], w, i);
adj[B[i]].emplace_back(A[i], w, i);
}
priority_queue<pair<ll, int>> pq;
vector<ll> dist(N, ll(1e18));
pq.emplace(-(dist[0] = 0), 0);
vector<int> par(N, -1);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop(); d *= -1;
if (d != dist[u]) continue;
for (auto [v, w, i] : adj[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
par[v] = i;
pq.emplace(-dist[v], v);
}
}
}
int u = T[p];
vector<int> path;
while (u != 0) {
path.push_back(par[u]);
u ^= A[par[u]] ^ B[par[u]];
}
reverse(all(path));
answer(path);
}
}
