버스

다가오는 선거를 앞두고 바이트버그 시는 새 버스 노선을 개통하기로 했습니다.

바이트버그에는 교차로 $n$개와 이 교차로들을 잇는 일방통행 도로 $m$개가 있습니다. 각 도로는 두 교차로를 잇는 곧은 선분이며, 중간에 굽은 구간이나 꺾인 구간이 전혀 없습니다. 한 도로에서 다른 도로로 갈아탈 수 있는 곳은 교차로뿐입니다. 두 도로가 교차로 없이 만난다면 한쪽은 터널이나 지하도로 지나가는 것이고, 두 도로가 겹친다면 한쪽은 고가도로로 지나가는 것입니다. 두 교차로는 여러 도로로 연결될 수 있으며, 이때 그 도로들은 서로 다른 도로로 봅니다.

각 도로의 버스 주행 시간은 이미 정해져 있고, 그 값은 항상 짝수 분입니다. 일부 도로에는 정류장이 있으며, 정류장은 항상 도로의 정확히 한가운데에 놓입니다. 즉 도로의 시작점에서 정류장까지 가는 시간과 정류장에서 도로의 끝점까지 가는 시간이 같습니다. 버스는 정해진 순서대로 정류장들을 지나야 합니다.

노선을 짜는 데에는 두 가지 제약이 있습니다.

첫째, 이 버스는 회전 반경이 커서, 교차로에서 회전각이 $90^\circ$ 이하일 때만 방향을 바꿀 수 있습니다.

버스가 화살표 방향으로 달릴 때 $\alpha$가 회전각입니다.

둘째, 첫 번째 정류장에서 마지막 정류장까지 가는 총 주행 시간을 최소로 만들어야 합니다. 버스는 정류장에서 실제로 멈추지는 않고, 각 정류장 옆을 지나가기만 하면 됩니다.

표준 입력에서 도시와 정류장 정보를 읽어 최적 노선을 찾고, 그 결과를 표준 출력에 출력하는 프로그램을 작성하세요.

첫째 줄에 정수 세 개 $n$, $m$, $p$가 공백으로 구분되어 주어집니다 ($3 \le n \le 50$, $2 \le m \le 500$, $2 \le p \le 100$). 각각 교차로의 수, 도로의 수, 정류장의 수입니다.

다음 $n$개의 줄에는 교차로가 하나씩 주어집니다. 그중 $i$번째 줄에는 정수 $x_i$와 $y_i$가 주어지며 ($-10000 \le x_i, y_i \le 10000$), 이는 $i$번 교차로의 좌표입니다. 교차로는 $1$번부터 $n$번까지 번호가 매겨져 있습니다.

다음 $m$개의 줄에는 도로가 하나씩 주어집니다. 각 줄에는 정수 $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$), $i$번 도로는 교차로 $a_i$에서 $b_i$로 향하고 주행 시간은 $2 \cdot t_i$분입니다. 도로는 $1$번부터 $m$번까지 번호가 매겨져 있습니다.

다음 $p$개의 줄에는 각 줄마다 정수 $e_i$가 하나씩 주어집니다 ($1 \le e_i \le m$). 이는 $i$번째 정류장이 놓인 도로의 번호입니다. 도로 번호는 중복될 수 있으며, 만약 $e_i = e_{i+1}$이면 버스는 정류장 $e_i$에서 출발해 한 바퀴 돌아 다시 그 정류장으로 돌아와야 합니다.

조건을 만족하는 노선이 없으면 NIE 한 단어만 출력합니다. 그렇지 않으면 $p-1$개의 줄을 출력합니다. $i$번째 줄에는, 버스가 최적 노선으로 달린다고 할 때 첫 번째 정류장에서 출발한 시각을 기준으로 $i+1$번째 정류장에 도착하는 시각을 출력합니다.

그림에서 원은 교차로를, 사각형은 정류장을 나타냅니다. 가는 선은 도로이고, 굵은 선은 첫 번째 정류장에서 두 번째 정류장으로 가는 가장 좋은 경로, 즉 최적 노선의 첫 구간입니다. 그림에서는 편의를 위해 각 도로의 주행 시간을 생략했습니다.