23329번 - 구슬 발사기 스페셜 저지

좌표 평면 위에 $N$개의 구슬 발사기가 있다. 발사기에서 발사된 구슬은 발사기를 만나기 전까지 무한히 이동한다. 구슬이 이동 중에 발사기를 만나면 발사기가 바라보는 방향으로 다시 발사되며, 발사기를 방문하지 않고 지나칠 수는 없다. 구슬 발사기는 북, 북동, 동, 남동, 남, 남서, 서, 북서 이렇게 $8$가지 방향을 바라볼 수 있다. 또한 발사기의 방향을 시계방향으로 원하는 만큼 회전시킬 수 있는데, 발사기 $i$를 $45$도 회전하기 위해 필요한 비용은 $c_{i}$이다. 발사기는 최대 한 번 구슬을 발사할 수 있다. 따라서 한 번 사용된 발사기에 구슬이 방문한다면 더 이상 구슬이 이동하지 않고 그 발사기에 멈춘다. 

발사기의 방향을 적절히 회전하여, 구슬을 발사기 $s$에서 발사기 $e$까지 최소 비용으로 도달하게 하려고 한다. 이 때 최소 비용과 어느 발사기를 거쳐서 이동했는지 구하는 프로그램을 작성하시오.

첫 번째 줄에 정수 $N$, $s$, $e$ 이 주어진다. ($2 \leq N \leq 100\,000, 1 \leq s, e \leq N, s \ne e$)

다음 $N$개의 줄에 걸쳐 발사기 $i$의 정보 $x_{i}$, $y_{i}$, $c_{i}$, $d_{i}$가 공백으로 분리되어 주어진다.

• $x_{i}$와 $y_{i}$는 각각 발사기 $i$의 $x$좌표와 $y$좌표이다. ($1 \leq x_i, y_i \leq 10^{9}$)
• $c_{i}$는 발사기 $i$를 회전하는데 필요한 비용이다. ($0 \leq c_i \leq 200\,000$)
• $d_{i}$는 발사기 $i$가 초기에 바라보고 있는 방향이다. 알파벳 대문자 N, NE, E, SE, S, SW, W, NW중 하나이며 각각 북, 북동, 동, 남동, 남, 남서, 서, 북서 방향을 의미한다.

서로 다른 두 발사기가 같은 좌표에 존재하지 않으며, 모든 $i$에 대하여 $x_i$, $y_i$, $c_i$는 정수이다.

첫 번째 줄에 최소 비용을 출력한다.

두 번째 줄에 발사기 $s$와 발사기 $e$를 포함하여, 이동한 발사기의 번호를 출력한다. 만약 최소 비용으로 이동할 수 있는 경로가 여러 가지라면 아무거나 출력한다.

만약 발사기 $e$까지 도달하는 것이 불가능하면, 첫 번째 줄에 $-1$을 출력한 뒤 종료한다.

동쪽이 $x$좌표가 증가하는 방향, 북쪽이 $y$좌표가 증가하는 방향이다.