Problem: Requirements

* All inputs are of non-negative integer value.
* T_{\text{max}} = 10000
* 200 \leq |V| \leq 400
* 1.5 |V| \leq |E| \leq 2 |V|
* 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
* 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
* The given graph has no self-loops / multiple edges and is guaranteed to be connected.
* 0 \leq N_{\text{new}} \leq 1
* 1 \leq \mathrm{new\\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}}). Note: If all orders are generated by the order generation rule as explained above, the total number of orders is at most T_{\text{last}}+1. Therefore, the possible range of \mathrm{new\\_id}_{i} should be from 1 to T_{\text{last}}+1.
* 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
* The order IDs \mathrm{new\\_{id}}_i are unique.

Input Format

Input is provided in the following form:


|V| |E|
u_{1} v_{1} d_{u_{1}, v_{1}}
u_{2} v_{2} d_{u_{2}, v_{2}}
:
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
T_{\text{max}}
\mathrm{info}_{0}
\mathrm{info}_{1}
:
\mathrm{info}_{T_{\text{max}}-1}


* In the first line |V| denotes the number of vertices, while |E| denotes the number of edges.
* The following |E| lines denote the edges of the graph. In particular, in the ith line u_{i} and v_{i} denote the edge connecting u_{i} and v_{i} and d_{u_{i}, v_{i}} the corresponding distance.
* The following line denotes the number of steps T_{\text{max}}.



In the following line, \mathrm{info}_t is information about the order from the customer that occurs at time t. \mathrm{info}_t is given in the form:


N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}


* N_{\text{new}} represents the number of new orders which appear at time t.
* The next N_{\text{new}} lines give the newly generated order information. The i-th order information indicates that the order ID \mathrm{new\\_{id}}_i of the new order, while \mathrm{dst}_i denotes the vertex to which the customer wishes the order to be delivered.
* Note: If N_{\text{new}}=0, there are no new lines.

Output Format

The Output expects T_{\text{max}} integers in the format specified below.


\mathrm{command}_{0}
\mathrm{command}_{1}
:
\mathrm{command}_{T_{\text{max}}-1}


In particular, \mathrm{command}_{i} shall specify the movement of the delivery car by using one of the following two options:

1) `stay`, if the car shall not move:


-1


2) `move w`, if the car shall be moved one step towards the neighboring vertex w


w


Note that in case of 2) w has to satisfy the following conditions:

* w \in V
* If the car is at vertex u: \left\\{ u, w \right\\} \in E .
* If the car is on the edge \left\\{ u, v \right\\}, w must either satisfy u = w or v = w.



* * *

Examples

Input




Output




Input

5 7
1 2 5
5 3 4
2 4 8
1 5 1
2 3 3
4 5 3
4 3 9
4
1
1 2
1
2 5
1
3 4
0


Output

2
-1
1
5

Solution (in CPP):

Solution:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


int dist[400][400];
int nxt_to[400][400];
int edge[400][400];

vector<vector<pair<int, int>>> order;

int lastTumi = -1;
vector<int> ordered_time[400];
tuple<int, int, int> cur;
set<int> donthave, having;


pair<int, int> dist_to(int u,int v,int d, int dst) { // on edge u-v dist d
	if (d == 0) {
		if (u == dst)return make_pair(0, -2);
		return make_pair(dist[u][dst], nxt_to[u][dst]);
	}
	else if (d + dist[u][dst] < edge[u][v] - d + dist[v][dst]){
		return make_pair(d + dist[u][dst], u);
	}
	else {
		return make_pair(edge[u][v] - d + dist[v][dst], v);
	}
}

tuple<int, int, int> move(const tuple<int, int, int>& cur, int dst) {
	if (dst == -2)return cur;
	int u, v, d;
	tie(u, v, d) = cur;
	if (u == dst) {
		d--;
		if (d == 0)return make_tuple(u, -1, 0);
		else return make_tuple(u, v, d);
	}
	else if (v == dst) {
		d++;
		if (d == edge[u][v])return make_tuple(v, -1, 0);
		else return make_tuple(u, v, d);
	}
	else {
		//assert(d == 0);
		if(edge[u][dst] > 1)return make_tuple(u, dst, 1);
		else return make_tuple(dst, -1, 0);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	// recieve |V| and |E|
	int V, E; std::cin >> V >> E;
	rep(u, V)rep(v, V)dist[u][v] = INF;
	memset(nxt_to, -1, sizeof(nxt_to));
	memset(edge, -1, sizeof(edge));

	for (int i = 0; i < E; i++) {
		// recieve edges
		int u, v, d; std::cin >> u >> v >> d;
		u--; v--;
		dist[u][v] = dist[v][u] = d;
		edge[u][v] = d;
		edge[v][u] = d;
	}
	rep(i, V)dist[i][i] = 0;
	rep(k, V)rep(i, V)rep(j, V)
		dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

	rep(i, V) {
		rep(j, V)if(edge[i][j] != -1){
			rep(k, V) {
				if (edge[i][j] + dist[j][k] == dist[i][k]) {
					nxt_to[i][k] = j;
				}
			}
		}
	}


	int Tmax; std::cin >> Tmax;
	order.resize(Tmax);

	cur = make_tuple(0, -1, 0);
	bool flag = false;

	// recieve info
	for (int i = 0; i < Tmax; i++) {
		int Nnew; std::cin >> Nnew;
		for (int j = 0; j < Nnew; j++) {
			int new_id, dst; std::cin >> new_id >> dst;
			order[i].emplace_back(new_id, dst);
		}
	}

	// insert your code here to get more meaningful output
	  // all stay
	for (int i = 0; i < Tmax; i++) {
		//std::cout << -1 << std::endl;

		for (auto p : order[i]) {
			int new_id, dst;
			tie(new_id, dst) = p;
			ordered_time[dst - 1].push_back(i);
			donthave.insert(dst - 1);
		}

		if (get<2>(cur) == 0 && get<0>(cur) == 0) {
			lastTumi = i;
			having.insert(all(donthave));
			donthave.clear();
			flag = false;
		}

		if (having.size()) {
			int u, v, d;
			tie(u, v, d) = cur;
			auto mi = make_pair(INF, -1);
			for (int dst: having) {
				mi = min(mi, dist_to(u, v, d, dst));
			}
			if(flag) mi = min(mi, dist_to(u, v, d, 0));

			cout << mi.second + 1 << endl;
			cur = move(cur, mi.second);
		}
		else {
			int u, v, d;
			tie(u, v, d) = cur;
			auto p = dist_to(u, v, d, 0);

			cout << p.second + 1 << endl;
			cur = move(cur, p.second);
		}

		if (get<2>(cur) == 0) {
			int u = get<0>(cur);
			while (ordered_time[u].size() && ordered_time[u].front() <= lastTumi) {
				ordered_time[u].erase(ordered_time[u].begin());
				flag = true;
			}
			having.erase(u);
		}
	}


	return 0;
}