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:
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<string>
#include <iomanip>
using namespace std;
typedef long long ll;

int Tmax, V, E, u, v, d, Nnew, new_id, dst, order[11111], check[444], par[444], sum = 0;
vector<vector<pair<int, int>>> li(444);
queue<pair<int, int>> route;
queue<int> store;
queue<int> car;

void dfs(int now, int distance) {
	route.push(make_pair(now, distance));
	sum += distance * 2;
	for (auto &e : li[now]) {
		if (par[e.first] == now) {
			dfs(e.first, e.second);
			route.push(make_pair(now, e.second));
		}
	}
}

int main() {
	cin >> V >> E;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> d;
		li[u].push_back(make_pair(v, d));
		li[v].push_back(make_pair(u, d));
	}
	cin >> Tmax;
	for (int i = 0; i < Tmax; i++) {
		cin >> Nnew;
		if (Nnew)
			cin >> new_id >> order[i];
		else
			order[i] = -1;
	}
	for (int i = 1; i <= V; i++)
		check[i] = 0;
	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int >>> que;
	que.push(make_pair(make_pair(0, 1), -1));
	while (!que.empty()) {
		int now = que.top().first.second, npar = que.top().second;
		que.pop();
		if (!check[now]) {
			check[now]++;
			par[now] = npar;
			for (auto &e : li[now]) {
				int next = e.first, dnext = e.second;
				if (!check[next])
					que.push(make_pair(make_pair(dnext, next), now));
			}
		}
	}
	dfs(1, 0);
	route.pop();
	int count = 0, ndst = 1, check_store = 1;
	queue<int> keep;
	queue<pair<int, int>> keep2;
	for (int i = 0; i < Tmax; i++) {
		if (order[i] > 0)
			store.push(order[i]);
		if (ndst == 1 && !count)
			check_store = 1;
		if (check_store) {
			while (!store.empty()) {
				car.push(store.front());
				store.pop();
			}
		}
		if (check_store&&car.size() < 1)
			cout << "-1" << endl;
		else {
			check_store = 0;
			if (!count) {
				while (!car.empty()) {
					if (car.front() != ndst)
						keep.push(car.front());
					car.pop();
				}
				while (!keep.empty()) {
					car.push(keep.front());
					keep.pop();
				}
				int nowp = ndst,flag=0;
				while (1) {
					int checkp = route.front().first;
					if (checkp == par[nowp])
						break;
					keep2.push(route.front());
					route.pop();
					while (!car.empty()) {
						if (car.front() == checkp) {
							flag = 1;
							break;
						}
						keep.push(car.front());
						car.pop();
					}
					while (!keep.empty()) {
						car.push(keep.front());
						keep.pop();
					}
					if (checkp == nowp) {
						if (flag) {
							while (!route.empty()) {
								keep2.push(route.front());
								route.pop();
							}
							while (!keep2.empty()) {
								route.push(keep2.front());
								keep2.pop();
							}
							break;
						}
						else {
							while (!keep2.empty()) {
								route.push(keep2.front());
								keep2.pop();
							}
						}
					}
				}
				ndst = route.front().first;
				count = route.front().second;
				route.pop();
				route.push(make_pair(ndst, count));
			}
			cout << ndst << endl;
			count--;
		}
	}
}