Bus

With an election approaching, the city of Byteburg has decided to launch a new bus line.

Byteburg has $n$ intersections and $m$ one-way streets connecting them. Each street is a straight segment joining two intersections, with no bends or curves along the way. Intersections are the only places where you can move from one street onto another: if two streets cross where there is no intersection, one of them runs through a tunnel or an underpass; if two streets overlap, one runs on a flyover. Two intersections may be joined by several streets, and such streets are treated as distinct.

The bus travel time is already fixed for every street, and it is always an even number of minutes. Some streets carry a bus stop, and a stop always sits exactly at the middle of its street, so the bus takes the same time from the start of the street to the stop as from the stop to the end. The bus must pass the stops in a fixed order.

Two constraints complicate the route.

First, the bus turns poorly: at an intersection it may change direction only when the turn angle is at most $90^\circ$.

If the bus travels in the direction of the arrow, then $\alpha$ is its turn angle.

Second, the total travel time from the first stop to the last stop must be minimized. The bus never actually stops at a stop; it only has to drive past each one.

Write a program that reads the description of the city and the planned stops, finds the optimal bus route, and prints the result to standard output.

The first line contains three integers $n$, $m$, $p$ ($3 \le n \le 50$, $2 \le m \le 500$, $2 \le p \le 100$): the number of intersections, the number of streets, and the number of planned stops.

Each of the next $n$ lines describes one intersection. Line $i$ of this block contains two integers $x_i$ and $y_i$ ($-10000 \le x_i, y_i \le 10000$): the coordinates of intersection $i$. Intersections are numbered from $1$ to $n$.

Each of the next $m$ lines describes one street with three integers $a_i$, $b_i$, $t_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le t_i \le 5000$): street $i$ runs from intersection $a_i$ to intersection $b_i$ and takes $2 \cdot t_i$ minutes to drive. Streets are numbered from $1$ to $m$.

Each of the next $p$ lines contains one integer $e_i$ ($1 \le e_i \le m$): the street on which the $i$-th stop lies. Street numbers may repeat; if $e_i = e_{i+1}$, the bus must leave stop $e_i$ and then return to it.

If no route satisfies the requirements, print a single word NIE. Otherwise print $p-1$ lines. Line $i$ contains the time at which the bus reaches the $(i+1)$-th stop, measured from its departure from the first stop, assuming it follows the optimal route.

In the figure, circles are intersections and squares are stops. Thin lines are streets; the thick line is the best possible route from the first stop to the second, that is, the first part of the optimal bus route. Street travel times are omitted from the figure for clarity.