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>
#include <chrono>
using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};



struct Timer{
	time_point<system_clock> start;
	Timer() : start(system_clock::now()) {}
	double seconds() {return duration<double>(system_clock::now() - start).count();}
};


struct Edge{
	int u, v, d;
};


struct Info{
	int id, u, t;
};


int T = 10000, V = 400, E = 800;
const int inf = 1000000000;
vector<Edge> G;
vector<Info> info;
vector<vector<int>> G2;
vector<bool> carry, delivered;
vector<int> ans;



void input(){
	cin >> V >> E;
	G.resize(E);
	G2.resize(V);
	rep(i,V){
		G2.at(i).resize(V);
		rep(j,V){
			G2.at(i).at(j) = inf;
		}
	}
	rep(i,E){
		cin >> G.at(i).u >> G.at(i).v >> G.at(i).d;
		G.at(i).u--;
		G.at(i).v--;
		G2[G.at(i).u][G.at(i).v] = G.at(i).d;
		G2[G.at(i).v][G.at(i).u] = G.at(i).d;
	}
	
	/*
	rep(k,V){
		rep(i,V){
			if(G2[i][k] == -1) continue;
			rep(j,V){
				if(G2[k][j] == -1) continue;
				G2[i][j] = min(G2[i][j], G2[i][k] + G2[k][j]);
			}
		}
	}
	*/
	
	cin >> T;
	rep(i,T){
		int n;cin >> n;
		if(n == 1){
			Info I;
			cin >> I.id >> I.u;
			I.u--;
			I.t = i;
			info.pb(I);
		}
	}
	ans.resize(T);
	rep(i,T) ans.at(i) = -2;
	carry.resize(info.size());
	delivered.resize(info.size());
	rep(i,info.size()){
		carry.at(i) = false;
		delivered.at(i) = false;
	}
}


void output(){
	rep(i,T){
		cout << ans.at(i) + 1 << endl;
	}
}


deque<int> order;


void solve(){
	rep(i,T){
		rep(j,info.size()){
			if(!delivered.at(j) && info[j].t <= i) carry.at(j) = true;
		}
		int mi = inf, num = 0;
		rep(j,info.size()){
			if(carry.at(j)){
				if(G2[0][info[j].u] < mi){
					mi = G2[0][info[j].u];
					num = info[j].u;
				}
			}
		}
		if(mi < inf){
			for(int j = 0; j < mi && i + j < T; j++){
				ans.at(i + j) = num;
			}
			i += mi;
			for(int j = 0; j < mi && i + j < T; j++){
				ans.at(i + j) = 0;
			}
			i += mi - 1;
		}
	}
}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	input();
	solve();
	output();
}