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 <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cerr << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int random(int l, int r)
{
	return l + rng() % (r - l + 1);
}

const int T = 10000 + 7;
int Tmax;
const int N = 400 + 7;
const int M = 800 + 7;

int n, m;
vector<PII> g[N];
pair<int, PII> edges[M];
PII order[T];
VI needed[N];
int dist[N][N];
int parent[N][N];
int G[N][N];
int number_of_orders_on_suf[T];
int TPeak;
int Tlast = 9500;

inline int waiting_orders(int l, int r)
{
	r = min(r, T - 1);
	if (l > r) return 0;
	return number_of_orders_on_suf[r] - (l ? number_of_orders_on_suf[l - 1] : 0);
}

void graph_input()
{
	cin >> n >> m;
	FOR(i, 1, n + 1) FOR(j, 1, n + 1) G[i][j] = INF;
	FOR(i, 1, n + 1) G[i][i] = 0;
	
	FOR(i, 0, m)
	{
		int u, v, w;
		cin >> u >> v >> w;
		G[u][v] = G[v][u] = w;
		g[u].PB({v, w});
		g[v].PB({u, w});
		edges[i] = {w, {u, v}};
	}
}

void order_input()
{
	cin >> Tmax;
	FILL(order, -1);
	double maxCoef = 0;
	int suma = 0;
	FOR(i, 0, Tmax)
	{
		int t;
		cin >> t;
		suma += t;
		if (suma / (i + 1.0) > maxCoef)
		{
			TPeak = i;
			maxCoef = suma / (i + 1.0);
		}
		
		if (i)
			number_of_orders_on_suf[i] = number_of_orders_on_suf[i - 1];
		if (t == 0) continue;
		number_of_orders_on_suf[i]++;
		int id, dst;
		cin >> id >> dst;
		order[i] = {id, dst};
		needed[dst].PB(i);		
	}
}

void preprocess()
{
	FOR(i, 1, n + 1)
	{
		FOR(j, 1, n + 1) dist[i][j] = INF;
		dist[i][i] = 0;
		set<PII> S;
		FOR(j, 1, n + 1)
			S.insert({dist[i][j], j});
		
		while(SZ(S))
		{
			int v = S.begin()->Y;
			S.erase(S.begin());
			
			for(auto e: g[v])
			{
				int to = e.X, len = e.Y;
				if (dist[i][to] <= dist[i][v] + len) continue;
				parent[i][to] = v;
				S.erase({dist[i][to], to});
				dist[i][to] = dist[i][v] + len;
				S.insert({dist[i][to], to});
			}
		}
	}
}

double probability(int curr_time)
{
	if (curr_time >= Tlast) return 0;
	if (curr_time >= TPeak)
		return (Tlast - curr_time) / (double)(Tlast - TPeak);
	else
		return curr_time / (double) TPeak;
}

vector<int> path(int from, int to)
{
	vector<int> res;
	while(from != to)
	{
		res.PB(to);
		to = parent[from][to];
	}
	
	res.PB(from);
	reverse(ALL(res));
	return res;
}

inline bool go_to_baza(int curr_vertex, int to, int start_time, int curr_time, 
	vector<int>& orders)
{
	if (dist[curr_vertex][to] > dist[curr_vertex][1] &&
		waiting_orders(start_time, curr_time) > 5) return true;
	if (2 * dist[curr_vertex][to] > dist[curr_vertex][1] && 
		curr_time - start_time >= 47) return true;
	
	if (5 * dist[curr_vertex][to] < dist[curr_vertex][1]) return false;
	
	if (abs(curr_time - TPeak) <= min(75, 4 * dist[curr_vertex][1]) && curr_time < TPeak) return true;
	
	return false;
}

int cnt[N];

vector<int> go(vector<int>& orders, int start_time)
{
	int curr_vertex = 1;
	vector<int> res;
	
	while(SZ(orders))
	{
		int to = -1;
		for(auto i: orders)
			cnt[order[i].Y] = 0;
		for(auto i: orders)
			cnt[order[i].Y]++;
		for(auto i: orders)
			if (to == -1 || dist[curr_vertex][to] * cnt[order[i].Y] > dist[curr_vertex][order[i].Y] * cnt[to])
				to = order[i].Y;
		
		if (curr_vertex != 1 && go_to_baza(curr_vertex, to, start_time, start_time + SZ(res), orders)) 
			to = 1;
					
		vector<int> way = path(curr_vertex, to);
		FOR(i, 0, SZ(way) - 1)
			FOR(j, 0, G[way[i]][way[i + 1]])
				res.PB(way[i + 1]);
		
		curr_vertex = to;
		sort(ALL(way));
		vector<int> nxt;
		for(auto i: orders)
		{
			auto it = lower_bound(ALL(way), order[i].Y);
			if (it != way.end() && *it == order[i].Y) continue;
			nxt.PB(i);
		}
		
		orders = nxt;
		if (to == 1) break;
	}	
	
	vector<int> way = path(curr_vertex, 1);
	FOR(i, 0, SZ(way) - 1)
		FOR(j, 0, G[way[i]][way[i + 1]])
			res.PB(way[i + 1]);
	
	return res;
}

int min_orders(int chas)
{
	if (abs(chas - TPeak) <= 200) return TPeak - chas;
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	graph_input();
	order_input();
	preprocess();
	
	vector<int> res;
	vector<int> orders;
	
	int chas = 0;
	while(chas < Tmax)
	{
		if (order[chas].X != -1)
			orders.PB(chas);
			
		if (SZ(orders) > min_orders(chas))
		{
			auto tut = go(orders, chas);
			for(auto i: tut) res.PB(i);
			if (SZ(res) >= Tmax)
			{
				res.resize(Tmax);
				break;
			}
			
			FOR(i, 0, SZ(tut))
			{
				chas++;
				if (order[chas].X != -1) orders.PB(chas);
			}
			
			continue;
		}
		
		chas++;		
		res.PB(-1);
	}
	
	for(auto i: res) cout << i << endl;
	
	//cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}