1 - Problem A

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

inputFormat

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.

outputFormat

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

样例

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

2
-1
1
5

</p>