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} should be from 1$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

见题面

见题面