#include "Annalib.h"
#include "Anna.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
#define pb push_back
#define llinf 1000000000000000LL
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
const ll maxn = 305;
ll n,m;
ll d[maxn][maxn];
ll d2[maxn][maxn];
ll b[2][6];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
n = N,m = M;
for(ll i = 1;i<=n;i++) {
for(ll j = 1;j<=n;j++) d[i][j] = d2[i][j] = llinf;
}
for(ll i = 1;i<=n;i++) d[i][i] = d2[i][i] = 0;
for(ll i = 1;i<=m;i++) {
ll x = A[i-1]+1,y = B[i-1]+1;
d[x][y] = d[y][x] = C[i-1];
bool oke = 1;
for(ll j = 0;j<K;j++) if(U[j]==i-1) oke =0;
if(oke) {
d2[x][y] = d2[y][x] = C[i-1];
}
}
for(ll k = 1;k<=n;k++) {
for(ll i = 1;i<=n;i++) {
for(ll j = 1;j<=n;j++) {
if(d[i][k]+d[k][j]<=d[i][j]) {
d[i][j] = d[i][k]+d[k][j];
}
if(d2[i][k]+d2[k][j]<=d2[i][j]) {
d2[i][j] = d2[i][k]+d2[k][j];
}
}
}
}
ll c = -1;
vector<ll> w;
if(K==1) c = A[U[0]];
else {
map<ll,ll> mp;
for(ll i = 0;i<K;i++) {
mp[A[U[i]]]++;
mp[B[U[i]]]++;
}
for(auto it : mp) {
if(it.sc>0) c = it.fi;
}
}
for(ll i = 0;i<K;i++) {
w.pb(A[U[i]]^B[U[i]]^c+1);
}
c++;
for(ll i = 1;i<=5;i++) for(ll e = 0;e<2;e++) b[e][i] =0 ;
for(ll i = 0;i<Q;i++) {
ll st = S[i]+1,en = T[i]+1;
ll mask = 0;
if(d[st][c]+d[c][en]==d[st][en]) {
if(d2[st][c]+d2[c][en]==d[st][en]) {
mask = 0;
}else {
for(ll j = 0;j<K;j++) {
ll e = w[j];
ll w = C[U[j]];
if(d2[st][e]+d2[c][en]+w==d[st][en]||d[st][c]+d2[e][en]+w==d[st][en]) mask = (1<<j);
}
for(ll j = 0;j<K;j++) {
for(ll f = 0;f<K;f++) {
if(f==j) continue;
ll e = w[j],r = w[f];
if(d2[st][e]+d2[r][en]+C[U[j]]+C[U[f]]==d[st][en]) mask = (1<<j)+(1<<f);
}
}
}
}
for(ll bit = 0;bit<=5;bit++) {
if((1<<bit)&i) b[1][bit]|=mask;
else b[0][bit]|=mask;
}
}
for(ll i = 0;i<=5;i++) {
for(ll j = 0;j<=5;j++) {
if((1<<j)&b[0][i]) Tap(1);
else Tap(0);
}
for(ll j = 0;j<=5;j++) {
if((1<<j)&b[1][i]) Tap(1);
else Tap(0);
}
}
}
#include "Brunolib.h"
#include "Bruno.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
#define pb push_back
#define all(a) a.begin(),a.end()
#define llinf 1000000000000000LL
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
ll n,m;
const ll maxn = 305;
ll d[maxn][maxn];
int last[maxn][maxn];
ll b[2][6];
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[]) {
n = N,m = M;
for(ll i = 1;i<=n;i++) {
for(ll j = 1;j<=n;j++) d[i][j] = llinf;
}
for(ll i = 1;i<=n;i++) d[i][i] = 0;
for(ll i = 1;i<=m;i++) {
bool oke = 1;
for(ll j = 0;j<K;j++) if(U[j]==i-1) oke =0;
if(!oke) continue;
ll x = A[i-1]+1,y = B[i-1]+1;
d[x][y] = d[y][x] = C[i-1];
last[x][y] = last[y][x] = i-1;
}
for(ll k = 1;k<=n;k++) {
for(ll i = 1;i<=n;i++) {
for(ll j = 1;j<=n;j++) {
if(d[i][k]+d[k][j]<d[i][j]) {
last[i][j] = last[k][j];
d[i][j] = d[i][k]+d[k][j];
}
}
}
}
ll c = -1;
vector<ll> w;
if(K==1) c = A[U[0]];
else {
map<ll,ll> mp;
for(ll i = 0;i<K;i++) {
mp[A[U[i]]]++;
mp[B[U[i]]]++;
}
for(auto it : mp) {
if(it.sc>0) c = it.fi;
}
}
for(ll i = 0;i<K;i++) {
w.pb(A[U[i]]^B[U[i]]^c+1);
}
c++;
ll csz = 0;
for(ll i = 0;i<=5;i++) {
b[0][i] = b[1][i] = 0;
for(ll j = 0;j<=5;j++) {
if(X[csz++]) b[0][i]+=(1<<j);
}
for(ll j = 0;j<=5;j++) {
if(X[csz++]) b[1][i]+=(1<<j);
}
}
for(ll j = 0;j<Q;j++) {
ll mask = 63;
for(ll bit = 0;bit<=5;bit++) {
if((1<<bit)&j) {
mask&=b[1][bit];
}else mask&=b[0][bit];
}
ll st = S[j]+1,en = T[j]+1;
if(mask==0){
vector<ll> ans = {};
while(st!=en){
ans.pb(last[st][en]);
ll id = last[st][en];
en--;
en = A[id]^B[id]^en;
en++;
}
reverse(all(ans));
for(ll x : ans) Answer(x);
}else if(__builtin_popcount(mask)==1){
ll e = -1;
ll g = c;
ll idi = -1;
for(ll j = 0;j<=5;j++) if((1<<j)&mask) e = w[j],idi = U[j];
if(d[st][e]+d[g][en]>d[st][g]+d[e][en]) swap(e,g);
vector<ll> ans = {};
//cerr<<"ab: "<<st<<" "<<e<< " "<<g<<" "<<en<< " "<<idi<<endl;
while(st!=e){
ans.pb(last[st][e]);
ll id = last[st][e];
e--;
e = A[id]^B[id]^e;
e++;
}
reverse(all(ans));
vector<ll> ans2 = {};
while(g!=en){
ans2.pb(last[g][en]);
ll id = last[g][en];
en--;
en = A[id]^B[id]^en;
en++;
}
reverse(all(ans2));
//cerr<<ans2.size()<<endl;
//cerr<<ans.size()<<endl;
for(ll x : ans) Answer(x);
Answer(idi);
for(ll x : ans2) Answer(x);
}else{
vector<ll> ve;
vector<ll> ee;
ll g = c;
for(ll j = 0;j<=5;j++) if((1<<j)&mask) ve.pb(w[j]),ee.pb(j);
if(d[st][ve[0]]+d[ve[1]][en]>d[st][ve[1]]+d[ve[0]][en]) swap(ve[0],ve[1]),swap(ee[0],ee[1]);
vector<ll> ans = {};
vector<ll> ans2 = {};
ll e = ve[0];
while(st!=e){
ans.pb(last[st][e]);
ll id = last[st][e];
e--;
e = A[id]^B[id]^e;
e++;
}
reverse(all(ans));
g = ve[1];
while(g!=en){
ans2.pb(last[g][en]);
ll id = last[g][en];
en--;
en = A[id]^B[id]^en;
en++;
}
reverse(all(ans2));
for(ll x : ans) Answer(x);
Answer(ee[0]);
Answer(ee[1]);
for(ll x : ans2) Answer(x);
}
Answer(-1);
}
}
