#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 998244353;
#define VQ vector<priority_queue<pair<ll,vector<int>>>>
#define VQQ vector<vector<pair<ll,vector<int>>>>

int V, E, T;
int deri[10500];
vector<pair<int, int>> G[405];
VVI kyori(401, VI(401, INF));
VVI prever(401, VI(401, -1));
vector<vector<vector<int>>> keiro(401, vector<vector<int>>(401));
int road[401][401];
int store_max = 500;
VI ans;
ll point = 0;
VI tmp;
ll sonshitu = 50000000LL;



//string fileName1 = "C:/Users/r/Desktop/toolkitA/scripts/sa11.in";
//std::ifstream ci(fileName1);
//string fileName = "C:/Users/r/Desktop/toolkitA/scripts/output.out";
//std::ofstream cou(fileName);

void nyuuryoku() {

	cin >> V >> E;
	REP(i, E) {
		int u, v, d;
		cin >> u >> v >> d;
		u--; v--;
		G[u].push_back({ v,d });
		G[v].push_back({ u,d });
		road[u][v] = d;
		road[v][u] = d;
	}
	cin >> T;

	REP(i, V) {
		sort(ALL(G[i]));
	}

	int cnt = 0;

	REP(i, T) {
		int n;
		cin >> n;
		if (n) {
			int id, dst;
			cnt++;
			cin >> id >> dst;
			dst--;
			deri[i] = dst;
		}
	}
}

void dijkstra(int s) {
	int vis[405];
	REP(i, V) vis[i] = 0;

	min_priority_queue<pair<ll, int>> que;

	kyori[s][s] = 0;
	que.push({ 0, s });

	while (!que.empty()) {
		auto q = que.top();
		que.pop();

		int cst = q.first;
		int cu = q.second;

		if (vis[cu]) continue;
		vis[cu] = 1;

		fore(p, G[cu]) {
			int cst2 = cst + p.second;
			int to = p.first;

			if (chmin(kyori[s][to], cst2)) {
				que.push({ kyori[s][to], to });
				prever[s][to] = cu;
			}
		}
	}
}

void get_path(int s, int t) {
	int tt = t;
	vector<int> path;
	while (1) {
		t = prever[s][t];
		if (s == t)break;
		path.push_back(t);
	}

	reverse(path.begin(), path.end());

	path.push_back(tt);

	for (int i : path) {
		keiro[s][tt] = path;
	}
}

void saitankeiro() {
	REP(i, V) {
		dijkstra(i);
	}


	REP(i, V)REP(j, V) {
		if (i == j)continue;
		get_path(i, j);
	}
}

//ansを更新する
void update(ll a) {
	if (a > point) {
		point = a;
		ans = tmp;
	}
}

//tmpに解答をいれて計算する
void calc() {

	ll cur = 0;
	ll cnt = 0;
	int now = 0;
	int dst = 0;

	VVI store(401);
	VVI car(401);
	VVI kara(401);
	VI kar;

	REP(i, T) {
		if (deri[i] != 0)store[deri[i]].push_back(i);
		if (tmp[i] == -1)continue;
		if (now == 0 && dst == 0) {
			REP(j, 401) {
				for (int k : store[j]) {
					car[j].push_back(k);
				}
			}
			store = kara;
		}

		if (now == tmp[i]) {
			dst--;
		}
		else {
			dst = kyori[now][tmp[i]] - 1;
			now = tmp[i];
		}
		if (dst == 0) {
			for (int j : car[now]) {
				cur -= (ll)((i - j + 1)*(i - j + 1));
			}
			cnt += car[now].size();
			car[now] = kar;

		}

	}
	update(cnt * 100000000LL + cur);
}



void beam_search6(int beam, int time_h) {

	VVI store(405);
	VVI car(405);
	VI kar;
	VVI kara(405);
	int now = 0;
	VI an;
	VI st(405, 0);
	VI ca(405, 0);
	bool check_9500 = true;

	REP(i, T) {
		if (deri[i] != 0) {
			st[deri[i]]++;
			store[deri[i]].push_back(i);
		}

		if (now == 0) {
			REP(j, V) {
				for (int k : store[j])car[j].push_back(k);
				ca[j] += st[j];
				st[j] = 0;
			}
			store = kara;
		}
		bool check_car = false;
		REP(j, V)if (ca[j] > 0)check_car = true;
		if (!check_car) {
			an.push_back(-1);
			continue;
		}
		int cnt = 0;

		VQQ q(time_h + 510);
		q[0].push_back({ 0, { 0 } });
		ll cur = 0;
		ll time_cur = 1000000;
		VI as;

		//cout << i << ' ' << i + time_h << endl;
		if ((i + time_h) < 9500) {
			REP(j, min(T - i, time_h + 500)) {
				int cu = 0;
				while (!q[j].empty()) {
					if (cu >= beam)break;
					cu++;
					ll point1 = q[j].back().first;
					VI v = q[j].back().second;
					VI vv = v;
					ll point3 = point1;
					q[j].pop_back();
					if (vv[vv.size() - 1] != 0) {
						ll aa = j + kyori[v[v.size() - 1]][0];
						VB check_ca(401, false);
						REP(k, V)if (ca[k] > 0)check_ca[k] = true;
						for (int k : vv)check_ca[k] = false;
						for (int k : keiro[v.back()][0]) {
							vv.push_back(k);
							if (check_ca[k]) {
								for (int l : car[k]) {
									point3 += 100000000LL;
									point3 -= (ll)((l - i - j - kyori[v.back()][k])*(l - i - j - kyori[v.back()][k]));
								}
							}
						}
						if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
							if (aa < time_h) {
								if (point3 > cur) {
									cur = point3;
									time_cur = aa;
									as = vv;
								}
							}
							else {
								if (point3*time_cur > aa*cur) {
									cur = point3;
									as = vv;
									time_cur = aa;
								}
							}
						}
					}


					VB check_c(401, false);
					REP(k, V)if (ca[k] != 0)check_c[k] = true;
					for (int k : v)check_c[k] = false;
					REP(k, V) {
						if (check_c[k]) {
							ll point2 = point1;
							for (int l : car[k])point2 += 100000000 - (ll)((i + j + kyori[k][v[v.size() - 1]] - l)*(i + j + kyori[k][v[v.size() - 1]] - l));
							VI vvv = v;
							vvv.push_back(k);
							if (j + kyori[k][v.back()] < time_h + 500) {
								int ti1 = j + kyori[k][v.back()];
								q[ti1].push_back({ point2,vvv });
								if (q[ti1].size() > beam) {
									sort(ALL(q[ti1]));
									reverse(ALL(q[ti1]));
									q[ti1].pop_back();
								}
							}
						}
					}
				}
			}
		}
		else {
			if (check_9500) {
				check_9500 = false;
				REP(j, 9500 - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll point3 = point1;
						q[j].pop_back();
						if (vv[vv.size() - 1] != 0) {
							ll aa = j + kyori[v[v.size() - 1]][0];
							VB check_ca(401, false);
							REP(k, V)if (ca[k] > 0)check_ca[k] = true;
							for (int k : vv)check_ca[k] = false;
							for (int k : keiro[v.back()][0]) {
								vv.push_back(k);
								if (check_ca[k]) {
									for (int l : car[k]) {
										point3 += 100000000LL;
										point3 -= (ll)((l - i - j - kyori[v.back()][k])*(l - i - j - kyori[v.back()][k]));
									}
								}
							}
							if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
								if (aa < time_h) {
									if (point3 > cur) {
										cur = point3;
										time_cur = aa;
										as = vv;
									}
								}
								else {
									if (point3*time_cur > aa*cur) {
										cur = point3;
										as = vv;
										time_cur = aa;
									}
								}
							}
						}


						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;
								for (int l : car[k])point2 += 100000000 - (ll)((i + j + kyori[k][v[v.size() - 1]] - l)*(i + j + kyori[k][v[v.size() - 1]] - l));
								VI vvv = v;
								vvv.push_back(k);
								if (j + kyori[k][v.back()] < time_h + 500) {
									int ti1 = j + kyori[k][v.back()];
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
			else {
				REP(j, T - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll point3 = point1;
						q[j].pop_back();
						if (cur < point3) {
							cur = point3;
							as = v;
						}
						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;
								for (int l : car[k])point2 += 100000000LL - (ll)((i + j + kyori[k][v.back()] - l)*(i + j + kyori[k][v.back()] - l));
								VI vvv = v;
								vvv.push_back(k);
								if (i + j + kyori[k][v.back()] < T) {
									int ti1 = j + kyori[k][v.back()];
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
		}
		if (cur == 0) {
			an.push_back(-1);
			continue;
		}

		int cntr = 0;
		as.erase(as.begin());
		for (int j : as) {
			for (int k : keiro[now][j]) {
				REP(l, kyori[now][k]) {
					an.push_back(k);
					cntr++;
				}
				now = k;
				ca[k] = 0;
				car[k] = kar;
			}
		}
		REP(j, max(0, cntr - 1)) {
			i++;
			if (deri[i] != 0) {
				st[deri[i]]++;
				store[deri[i]].push_back(i);
			}
		}
	}

	tmp = an;
}


//0に帰るときに同じ長さで隣にあるなら行ってみる。
void beam_search7(int beam, int time_h, int time_loss) {

	VVI store(405);
	VVI car(405);
	VI kar;
	VVI kara(405);
	int now = 0;
	VI an;
	VI st(405, 0);
	VI ca(405, 0);
	bool check_9500 = true;

	REP(i, T) {
		if (deri[i] != 0) {
			st[deri[i]]++;
			store[deri[i]].push_back(i);
		}

		if (now == 0) {
			REP(j, V) {
				for (int k : store[j])car[j].push_back(k);
				ca[j] += st[j];
				st[j] = 0;
			}
			store = kara;
		}
		bool check_car = false;
		REP(j, V)if (ca[j] > 0)check_car = true;
		if (!check_car) {
			an.push_back(-1);
			continue;
		}
		int cnt = 0;

		VQQ q(time_h + 510);
		q[0].push_back({ 0, { 0 } });
		ll cur = 0;
		ll time_cur = 1000000;
		VI as;

		//cout << i << ' ' << i + time_h << endl;
		if ((i + time_h) < 9500) {
			REP(j, min(T - i, time_h + 500)) {
				int cu = 0;
				while (!q[j].empty()) {
					if (cu >= beam)break;
					cu++;
					ll point1 = q[j].back().first;
					VI v = q[j].back().second;
					VI vv = v;
					ll point3 = point1;
					
					q[j].pop_back();
					if (vv[vv.size() - 1] != 0) {
						ll aa = j + kyori[v[v.size() - 1]][0];
						ll aaa = j;
						VI vvv = v;
						ll point4 = point1;
						VB check_ca(401, false);
						REP(k, V)if (ca[k] > 0)check_ca[k] = true;
						for (int k : vv)check_ca[k] = false;
						for (int k : keiro[v.back()][0]) {
							vv.push_back(k);
							if (check_ca[k]) {
								for (int l : car[k]) {
									point3 += 100000000LL;
									ll ab = (l - i - j - kyori[v.back()][k]);
									point3 -= ab * ab;
								}
							}
						}
						if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
							if (aa < time_h) {
								if (point3 > cur) {
									cur = point3;
									time_cur = aa;
									as = vv;
								}
							}
							else {
								if (point3*time_cur > aa*cur) {
									cur = point3;
									as = vv;
									time_cur = aa;
								}
							}
						}
						//=======================================================================================================
						now = v.back();
						while (now != 0) {
							if (check_ca[keiro[now][0][0]]) {
								aaa += kyori[now][keiro[now][0][0]];
								for (int l : car[keiro[now][0][0]]) {
									point4 += 100000000LL;
									ll ab = (l - i - aaa);
									point4 -= ab * ab;
								}
								vvv.push_back(keiro[now][0][0]);
								now = keiro[now][0][0];
								check_ca[now] = false;
							}
							else {
								bool b = true;
								for (pair<int, int> k : G[now]) {
									if (check_ca[k.first]) {
										if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
											aaa += kyori[now][k.first];
											for (int l : car[k.first]) {
												point4 += 100000000LL;
												ll ab = (l - i - aaa);
												point4 -= ab * ab;
											}
											vvv.push_back(k.first);
											now = k.first;
											check_ca[now] = false;
											b = false;
											break;
										}
									}
								}
								if (b) {
									aaa += kyori[now][keiro[now][0][0]];
									now = keiro[now][0][0];
									vvv.push_back(now);
									check_ca[now] = false;
								}
							}
						}
						if (i +aaa < 9525) {
							if (aaa < time_h) {
								if (point4 > cur) {
									cur = point4;
									time_cur = aaa;
									as = vvv;
								}
							}
							else {
								if (point4*time_cur > aaa*cur) {
									cur = point4;
									as = vvv;
									time_cur = aaa;
								}
							}
						}
						//=======================================================================================================
					}



					VB check_c(401, false);
					REP(k, V)if (ca[k] != 0)check_c[k] = true;
					for (int k : v)check_c[k] = false;
					REP(k, V) {
						if (check_c[k]) {
							ll point2 = point1;
							for (int l : car[k]) {
								ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
								point2 += 100000000;
								point2 -= ab * ab;
							}
							VI vvv = v;
							vvv.push_back(k);
							if (j + kyori[k][v.back()] < time_h + 500) {
								int ti1 = j + kyori[k][v.back()];
								q[ti1].push_back({ point2,vvv });
								if (q[ti1].size() > beam) {
									sort(ALL(q[ti1]));
									reverse(ALL(q[ti1]));
									q[ti1].pop_back();
								}
							}
						}
					}
				}
			}
		}
		else {
			if (check_9500) {
				check_9500 = false;
				REP(j, 9500 - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll aaa = j;
						VI vvv = v;
						ll point3 = point1;
						ll point4 = point1;
						q[j].pop_back();
						if (vv[vv.size() - 1] != 0) {
							ll aa = j + kyori[v[v.size() - 1]][0];
							VB check_ca(401, false);
							REP(k, V)if (ca[k] > 0)check_ca[k] = true;
							for (int k : vv)check_ca[k] = false;
							for (int k : keiro[v.back()][0]) {
								vv.push_back(k);
								if (check_ca[k]) {
									for (int l : car[k]) {
										point3 += 100000000LL;
										ll ab = l - i - j - kyori[v.back()][k];
										point3 -= ab * ab;
									}
								}
							}
							if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
								if (aa < time_h) {
									if (point3 > cur) {
										cur = point3;
										time_cur = aa;
										as = vv;
									}
								}
								else {
									if (point3*time_cur > aa*cur) {
										cur = point3;
										as = vv;
										time_cur = aa;
									}
								}
							}
							//=======================================================================================================
							now = v.back();
							while (now != 0) {
								if (check_ca[keiro[now][0][0]]) {
									aaa += kyori[now][keiro[now][0][0]];
									for (int l : car[keiro[now][0][0]]) {
										point4 += 100000000LL;
										ll ab = (l - i - aaa);
										point4 -= ab * ab;
									}
									vvv.push_back(keiro[now][0][0]);
									now = keiro[now][0][0];
									check_ca[now] = false;
								}
								else {
									bool b = true;
									for (pair<int, int> k : G[now]) {
										if (check_ca[k.first]) {
											if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
												aaa += kyori[now][k.first];
												for (int l : car[k.first]) {
													point4 += 100000000LL;
													ll ab = (l - i - aaa);
													point4 -= ab * ab;
												}
												vvv.push_back(k.first);
												now = k.first;
												b = false;
												check_ca[now] = false;
												break;
											}
										}
									}
									if (b) {
										aaa += kyori[now][keiro[now][0][0]];
										now = keiro[now][0][0];
										vvv.push_back(now);
										check_ca[now] = false;
									}
								}
							}
							if (i + aaa < 9525) {
								if (aaa < time_h) {
									if (point4 > cur) {
										cur = point4;
										time_cur = aaa;
										as = vvv;
									}
								}
								else {
									if (point4*time_cur > aaa*cur) {
										cur = point4;
										as = vvv;
										time_cur = aaa;
									}
								}
							}
							//=======================================================================================================
						}


						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;
								
								for (int l : car[k]) {
									point2 += 100000000;
									ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
									point2 -= ab * ab;
								}

								VI vvv = v;
								vvv.push_back(k);
								if (j + kyori[k][v.back()] < time_h + 500) {
									int ti1 = j + kyori[k][v.back()];
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
			else {
				REP(j, T - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll point3 = point1;
						q[j].pop_back();
						if (cur < point3) {
							cur = point3;
							as = v;
						}
						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;
								for (int l : car[k]) {
									point2 += 100000000LL;
									ll ab = i + j + kyori[k][v.back()] - l;
									point2 -= ab * ab;
								}
								VI vvv = v;
								vvv.push_back(k);
								if (i + j + kyori[k][v.back()] < T) {
									int ti1 = j + kyori[k][v.back()];
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
		}
		if (cur == 0) {
			an.push_back(-1);
			continue;
		}

		int cntr = 0;
		as.erase(as.begin());
		for (int j : as) {
			for (int k : keiro[now][j]) {
				REP(l, kyori[now][k]) {
					an.push_back(k);
					cntr++;
				}
				now = k;
				ca[k] = 0;
				car[k] = kar;
			}
		}
		REP(j, max(0, cntr - 1)) {
			i++;
			if (deri[i] != 0) {
				st[deri[i]]++;
				store[deri[i]].push_back(i);
			}
		}
	}

	tmp = an;
}


//0に帰るときに同じ長さで隣にあるなら行ってみる。
void beam_search8(int beam, int time_h, int time_loss) {

	VVI store(405);
	VVI car(405);
	VI kar;
	VVI kara(405);
	int now = 0;
	VI an;
	VI st(405, 0);
	VI ca(405, 0);
	bool check_9500 = true;

	REP(i, T) {
		if (deri[i] != 0) {
			st[deri[i]]++;
			store[deri[i]].push_back(i);
		}

		if (now == 0) {
			REP(j, V) {
				for (int k : store[j])car[j].push_back(k);
				ca[j] += st[j];
				st[j] = 0;
			}
			store = kara;
		}
		bool check_car = false;
		REP(j, V)if (ca[j] > 0)check_car = true;
		if (!check_car) {
			an.push_back(-1);
			continue;
		}
		int cnt = 0;

		VQQ q(time_h + 510);
		q[0].push_back({ 0, { 0 } });
		ll cur = 0;
		ll time_cur = 1000000;
		VI as;

		//cout << i << ' ' << i + time_h << endl;
		if ((i + time_h) < 9500) {
			REP(j, min(T - i, time_h + 500)) {
				int cu = 0;
				while (!q[j].empty()) {
					if (cu >= beam)break;
					cu++;
					ll point1 = q[j].back().first;
					VI v = q[j].back().second;
					VI vv = v;
					ll point3 = point1;

					q[j].pop_back();
					if (vv[vv.size() - 1] != 0) {
						ll aa = j + kyori[v[v.size() - 1]][0];
						ll aaa = j;
						VI vvv = v;
						ll point4 = point1;
						VB check_ca(401, false);
						REP(k, V)if (ca[k] > 0)check_ca[k] = true;
						for (int k : vv)check_ca[k] = false;
						for (int k : keiro[v.back()][0]) {
							vv.push_back(k);
							if (check_ca[k]) {
								for (int l : car[k]) {
									point3 += 100000000LL;
									ll ab = (l - i - j - kyori[v.back()][k]);
									point3 -= ab * ab;
								}
							}
						}
						if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
							if (aa < time_h) {
								if (point3 > cur) {
									cur = point3;
									time_cur = aa;
									as = vv;
								}
							}
							else {
								if (point3*time_cur > aa*cur) {
									cur = point3;
									as = vv;
									time_cur = aa;
								}
							}
						}
						//=======================================================================================================
						now = v.back();
						while (now != 0) {
							priority_queue<pair<ll,pair<ll, int>>> qp;
							qp.push({ 0,{0,keiro[now][0][0]} });
							for (pair<int, int> k : G[now]) {
								if (check_ca[k.first]) {
									if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
										ll point5 = 0;
										ll point6 = 0;
										ll aaaa = aaa + kyori[now][k.first];
										for (int l : car[k.first]) {
											point5 += 100000000LL;
											point6 += 100000000LL;
											ll ab = (l - i - aaaa);
											point5 += ab * ab;
											point6 -= ab * ab;

										}
										qp.push({ point5,{point6,k.first} });
									}
								}
							}
							aaa += kyori[qp.top().second.second][now];
							point4 += qp.top().second.first;
							now = qp.top().second.second;
							check_ca[now] = false;
							vvv.push_back(now);
						}
						if (i + aaa < 9525) {
							if (aaa < time_h) {
								if (point4 > cur) {
									cur = point4;
									time_cur = aaa;
									as = vvv;
								}
							}
							else {
								if (point4*time_cur > aaa*cur) {
									cur = point4;
									as = vvv;
									time_cur = aaa;
								}
							}
						}
						//=======================================================================================================
					}



					VB check_c(401, false);
					REP(k, V)if (ca[k] != 0)check_c[k] = true;
					for (int k : v)check_c[k] = false;
					REP(k, V) {
						if (check_c[k]) {
							ll point2 = point1;
							for (int l : car[k]) {
								ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
								point2 += 100000000;
								point2 -= ab * ab;
							}
							VI vvv = v;
							vvv.push_back(k);
							if (j + kyori[k][v.back()] < time_h + 500) {
								int ti1 = j + kyori[k][v.back()];
								q[ti1].push_back({ point2,vvv });
								if (q[ti1].size() > beam) {
									sort(ALL(q[ti1]));
									reverse(ALL(q[ti1]));
									q[ti1].pop_back();
								}
							}
						}
					}
				}
			}
		}
		else {
			if (check_9500) {
				check_9500 = false;
				REP(j, 9500 - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll aaa = j;
						VI vvv = v;
						ll point3 = point1;
						ll point4 = point1;
						q[j].pop_back();
						if (vv[vv.size() - 1] != 0) {
							ll aa = j + kyori[v[v.size() - 1]][0];
							VB check_ca(401, false);
							REP(k, V)if (ca[k] > 0)check_ca[k] = true;
							for (int k : vv)check_ca[k] = false;
							for (int k : keiro[v.back()][0]) {
								vv.push_back(k);
								if (check_ca[k]) {
									for (int l : car[k]) {
										point3 += 100000000LL;
										ll ab = l - i - j - kyori[v.back()][k];
										point3 -= ab * ab;
									}
								}
							}
							if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
								if (aa < time_h) {
									if (point3 > cur) {
										cur = point3;
										time_cur = aa;
										as = vv;
									}
								}
								else {
									if (point3*time_cur > aa*cur) {
										cur = point3;
										as = vv;
										time_cur = aa;
									}
								}
							}
							//=======================================================================================================
							now = v.back();
							while (now != 0) {
								priority_queue<pair<ll, pair<ll, int>>> qp;
								qp.push({ 0,{0,keiro[now][0][0]} });
								for (pair<int, int> k : G[now]) {
									if (check_ca[k.first]) {
										if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
											ll point5 = 0;
											ll point6 = 0;
											ll aaaa = aaa + kyori[now][k.first];
											for (int l : car[k.first]) {
												point5 += 100000000LL;
												point6 += 100000000LL;
												ll ab = (l - i - aaaa);
												point5 += ab * ab;
												point6 -= ab * ab;

											}
											qp.push({ point5,{point6,k.first} });
										}
									}
								}
								aaa += kyori[qp.top().second.second][now];
								point4 += qp.top().second.first;
								now = qp.top().second.second;
								check_ca[now] = false;
								vvv.push_back(now);
							}
							if (i + aaa < 9525) {
								if (aaa < time_h) {
									if (point4 > cur) {
										cur = point4;
										time_cur = aaa;
										as = vvv;
									}
								}
								else {
									if (point4*time_cur > aaa*cur) {
										cur = point4;
										as = vvv;
										time_cur = aaa;
									}
								}
							}
							//=======================================================================================================
						}


						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;

								for (int l : car[k]) {
									point2 += 100000000;
									ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
									point2 -= ab * ab;
								}

								VI vvv = v;
								vvv.push_back(k);
								if (j + kyori[k][v.back()] < time_h + 500) {
									int ti1 = j + kyori[k][v.back()];
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
			else {
				REP(j, T - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll point3 = point1;
						q[j].pop_back();
						if (cur < point3) {
							cur = point3;
							as = v;
						}
						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;
								for (int l : car[k]) {
									point2 += 100000000LL;
									ll ab = i + j + kyori[k][v.back()] - l;
									point2 -= ab * ab;
								}
								VI vvv = v;
								vvv.push_back(k);
								if (i + j + kyori[k][v.back()] < T) {
									int ti1 = j + kyori[k][v.back()];
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
		}
		if (cur == 0) {
			an.push_back(-1);
			continue;
		}

		int cntr = 0;
		as.erase(as.begin());
		for (int j : as) {
			for (int k : keiro[now][j]) {
				REP(l, kyori[now][k]) {
					an.push_back(k);
					cntr++;
				}
				now = k;
				ca[k] = 0;
				car[k] = kar;
			}
		}
		REP(j, max(0, cntr - 1)) {
			i++;
			if (deri[i] != 0) {
				st[deri[i]]++;
				store[deri[i]].push_back(i);
			}
		}
	}

	tmp = an;
}

void beam_search9(int beam, int time_h, int time_loss) {

	VVI store(405);
	VVI car(405);
	VI kar;
	VVI kara(405);
	int now = 0;
	VI an;
	VI st(405, 0);
	VI ca(405, 0);
	bool check_9500 = true;

	REP(i, T) {
		if (deri[i] != 0) {
			st[deri[i]]++;
			store[deri[i]].push_back(i);
		}

		if (now == 0) {
			REP(j, V) {
				for (int k : store[j])car[j].push_back(k);
				ca[j] += st[j];
				st[j] = 0;
			}
			store = kara;
		}
		bool check_car = false;
		REP(j, V)if (ca[j] > 0)check_car = true;
		if (!check_car) {
			an.push_back(-1);
			continue;
		}
		int cnt = 0;

		VQQ q(time_h + 510);
		q[0].push_back({ 0, { 0 } });
		ll cur = 0;
		ll time_cur = 1000000;
		VI as;

		//cout << i << ' ' << i + time_h << endl;
		if ((i + time_h) < 9500) {
			REP(j, min(T - i, time_h + 500)) {
				int cu = 0;
				while (!q[j].empty()) {
					if (cu >= beam)break;
					cu++;
					ll point1 = q[j].back().first;
					VI v = q[j].back().second;
					VI vv = v;
					ll point3 = point1;

					q[j].pop_back();
					if (vv[vv.size() - 1] != 0) {
						ll aa = j + kyori[v[v.size() - 1]][0];
						ll aaa = j;
						VI vvv = v;
						ll point4 = point1;
						VB check_ca(401, false);
						REP(k, V)if (ca[k] > 0)check_ca[k] = true;
						for (int k : vv)check_ca[k] = false;
						for (int k : keiro[v.back()][0]) {
							vv.push_back(k);
							if (check_ca[k]) {
								for (int l : car[k]) {
									point3 += 100000000LL;
									ll ab = (l - i - j - kyori[v.back()][k]);
									point3 -= ab * ab;
								}
							}
						}
						if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
							if (aa < time_h) {
								if (point3 > cur) {
									cur = point3;
									time_cur = aa;
									as = vv;
								}
							}
							else {
								if (point3*time_cur > aa*cur) {
									cur = point3;
									as = vv;
									time_cur = aa;
								}
							}
						}
						now = v.back();
						while (now != 0) {
							priority_queue<pair<ll, pair<ll, int>>> qp;
							qp.push({ 0,{0,keiro[now][0][0]} });
							for (pair<int, int> k : G[now]) {
								if (check_ca[k.first]) {
									if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
										ll point5 = 0;
										ll point6 = 0;
										ll aaaa = aaa + kyori[now][k.first];
										for (int l : car[k.first]) {
											point5 += 100000000LL;
											point6 += 100000000LL;
											ll ab = (l - i - aaaa);
											point5 += ab * ab;
											point6 -= ab * ab;

										}
										qp.push({ point5,{point6,k.first} });
									}
								}
							}
							aaa += kyori[qp.top().second.second][now];
							point4 += qp.top().second.first;
							now = qp.top().second.second;
							check_ca[now] = false;
							vvv.push_back(now);
						}
						if (i + aaa < 9525) {
							if (aaa < time_h) {
								if (point4 > cur) {
									cur = point4;
									time_cur = aaa;
									as = vvv;
								}
							}
							else {
								if (point4*time_cur > aaa*cur) {
									cur = point4;
									as = vvv;
									time_cur = aaa;
								}
							}
						}
					}



					//=======================================================================================================



					VB check_c(401, false);
					REP(k, V)if (ca[k] != 0)check_c[k] = true;
					for (int k : v)check_c[k] = false;
					REP(k, V) {
						if (check_c[k]) {
							ll point2 = point1;
							for (int l : car[k]) {
								ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
								point2 += 100000000;
								point2 -= ab * ab;
							}
							VI vvv = v;
							vvv.push_back(k);
							if (j + kyori[k][v.back()] < time_h + 500) {
								bool b = true;
								int ti1 = j + kyori[k][v.back()];
								REP(l, q[ti1].size()) {
									if (q[ti1][l].second.back() == k) {
										VI vvv1 = vvv;
										VI vvv2 = q[ti1][l].second;
										sort(ALL(vvv1));
										sort(ALL(vvv2));
										if (vvv1 == vvv2) {
											b = false;
											if (point2 > q[ti1][l].first) {
												q[ti1][l] = { point2,vvv };
												sort(ALL(q[ti1]));
												reverse(ALL(q[ti1]));
											}
											break;
										}
									}
								}
								if (b) {
									q[ti1].push_back({ point2,vvv });
									if (q[ti1].size() > beam) {
										sort(ALL(q[ti1]));
										reverse(ALL(q[ti1]));
										q[ti1].pop_back();
									}
								}
							}
						}
					}
				}
			}
		}
		else {
			if (check_9500) {
				check_9500 = false;
				REP(j, 9500 - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll aaa = j;
						VI vvv = v;
						ll point3 = point1;
						ll point4 = point1;
						q[j].pop_back();
						if (vv[vv.size() - 1] != 0) {
							ll aa = j + kyori[v[v.size() - 1]][0];
							VB check_ca(401, false);
							REP(k, V)if (ca[k] > 0)check_ca[k] = true;
							for (int k : vv)check_ca[k] = false;
							for (int k : keiro[v.back()][0]) {
								vv.push_back(k);
								if (check_ca[k]) {
									for (int l : car[k]) {
										point3 += 100000000LL;
										ll ab = l - i - j - kyori[v.back()][k];
										point3 -= ab * ab;
									}
								}
							}
							if (i + j + kyori[v[v.size() - 1]][0] < 9525) {
								if (aa < time_h) {
									if (point3 > cur) {
										cur = point3;
										time_cur = aa;
										as = vv;
									}
								}
								else {
									if (point3*time_cur > aa*cur) {
										cur = point3;
										as = vv;
										time_cur = aa;
									}
								}
							}
							now = v.back();
							while (now != 0) {
								priority_queue<pair<ll, pair<ll, int>>> qp;
								qp.push({ 0,{0,keiro[now][0][0]} });
								for (pair<int, int> k : G[now]) {
									if (check_ca[k.first]) {
										if (kyori[now][k.first] + kyori[k.first][0] - kyori[now][0] <= time_loss) {
											ll point5 = 0;
											ll point6 = 0;
											ll aaaa = aaa + kyori[now][k.first];
											for (int l : car[k.first]) {
												point5 += 100000000LL;
												point6 += 100000000LL;
												ll ab = (l - i - aaaa);
												point5 += ab * ab;
												point6 -= ab * ab;

											}
											qp.push({ point5,{point6,k.first} });
										}
									}
								}
								aaa += kyori[qp.top().second.second][now];
								point4 += qp.top().second.first;
								now = qp.top().second.second;
								check_ca[now] = false;
								vvv.push_back(now);
							}
							if (i + aaa < 9525) {
								if (aaa < time_h) {
									if (point4 > cur) {
										cur = point4;
										time_cur = aaa;
										as = vvv;
									}
								}
								else {
									if (point4*time_cur > aaa*cur) {
										cur = point4;
										as = vvv;
										time_cur = aaa;
									}
								}
							}
						}




						//=======================================================================================================





						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;

								for (int l : car[k]) {
									point2 += 100000000;
									ll ab = i + j + kyori[k][v[v.size() - 1]] - l;
									point2 -= ab * ab;
								}

								VI vvv = v;
								vvv.push_back(k);
								if (j + kyori[k][v.back()] < time_h + 500) {
									bool b = true;
									int ti1 = j + kyori[k][v.back()];
									REP(l, q[ti1].size()) {
										if (q[ti1][l].second.back() == k) {
											VI vvv1 = vvv;
											VI vvv2 = q[ti1][l].second;
											sort(ALL(vvv1));
											sort(ALL(vvv2));
											if (vvv1 == vvv2) {
												b = false;
												if (point2 > q[ti1][l].first) {
													q[ti1][l] = { point2,vvv };
													sort(ALL(q[ti1]));
													reverse(ALL(q[ti1]));
												}
												break;
											}
										}
									}
									if (b) {
										q[ti1].push_back({ point2,vvv });
										if (q[ti1].size() > beam) {
											sort(ALL(q[ti1]));
											reverse(ALL(q[ti1]));
											q[ti1].pop_back();
										}
									}
								}
							}
						}
					}
				}
			}
			else {
				REP(j, T - i) {
					int cu = 0;
					while (!q[j].empty()) {
						if (cu >= beam)break;
						cu++;
						ll point1 = q[j].back().first;
						VI v = q[j].back().second;
						VI vv = v;
						ll point3 = point1;
						q[j].pop_back();
						if (cur < point3) {
							cur = point3;
							as = v;
						}
						VB check_c(401, false);
						REP(k, V)if (ca[k] != 0)check_c[k] = true;
						for (int k : v)check_c[k] = false;
						REP(k, V) {
							if (check_c[k]) {
								ll point2 = point1;
								for (int l : car[k]) {
									point2 += 100000000LL;
									ll ab = i + j + kyori[k][v.back()] - l;
									point2 -= ab * ab;
								}
								VI vvv = v;
								vvv.push_back(k);
								if (i + j + kyori[k][v.back()] < T) {
									bool b = true;
									int ti1 = j + kyori[k][v.back()];
									REP(l, q[ti1].size()) {
										if (q[ti1][l].second.back() == k) {
											VI vvv1 = vvv;
											VI vvv2 = q[ti1][l].second;
											sort(ALL(vvv1));
											sort(ALL(vvv2));
											if (vvv1 == vvv2) {
												b = false;
												if (point2 > q[ti1][l].first) {
													q[ti1][l] = { point2,vvv };
													sort(ALL(q[ti1]));
													reverse(ALL(q[ti1]));
												}
												break;
											}
										}
									}
									if (b) {
										q[ti1].push_back({ point2,vvv });
										if (q[ti1].size() > beam) {
											sort(ALL(q[ti1]));
											reverse(ALL(q[ti1]));
											q[ti1].pop_back();
										}
									}
								}
							}
						}
					}
				}
			}
		}
		if (cur == 0) {
			an.push_back(-1);
			continue;
		}

		int cntr = 0;
		as.erase(as.begin());
		for (int j : as) {
			for (int k : keiro[now][j]) {
				REP(l, kyori[now][k]) {
					an.push_back(k);
					cntr++;
				}
				now = k;
				ca[k] = 0;
				car[k] = kar;
			}
		}
		REP(j, max(0, cntr - 1)) {
			i++;
			if (deri[i] != 0) {
				st[deri[i]]++;
				store[deri[i]].push_back(i);
			}
		}
	}

	tmp = an;
}



int main() {

	nyuuryoku();

	saitankeiro();


	beam_search9(8, 100, 100);
	calc();


	REP(i, 10000) {
		if (ans[i] != -1)cout << ans[i] + 1 << endl;
		else cout << -1 << endl;
	}


}

Measured memory_bytes: 21024