Marble Launchers

There are $N$ marble launchers on the coordinate plane. A marble fired from a launcher travels infinitely until it meets a launcher. If the marble meets a launcher while moving, it is fired again in the direction the launcher faces, and it cannot pass by a launcher without visiting it. A marble launcher can face one of $8$ directions: north, northeast, east, southeast, south, southwest, west, and northwest. You can also rotate a launcher clockwise by any amount, and the cost to rotate launcher $i$ by $45$ degrees is $c_{i}$. A launcher can fire a marble at most once. Therefore, if a marble visits a launcher that has already been used, the marble stops at that launcher and moves no further.

By rotating the launchers appropriately, you want the marble to travel from launcher $s$ to launcher $e$ at minimum cost. Write a program that finds the minimum cost and which launchers the marble passed through.

The first line gives the integers $N$, $s$, and $e$. ($2 \leq N \leq 100\,000, 1 \leq s, e \leq N, s \ne e$)

The next $N$ lines give the information for launcher $i$: $x_{i}$, $y_{i}$, $c_{i}$, and $d_{i}$, separated by spaces.

• $x_{i}$ and $y_{i}$ are the $x$-coordinate and $y$-coordinate of launcher $i$. ($1 \leq x_i, y_i \leq 10^{9}$)
• $c_{i}$ is the cost to rotate launcher $i$. ($0 \leq c_i \leq 200\,000$)
• $d_{i}$ is the direction launcher $i$ initially faces. It is one of the uppercase strings N, NE, E, SE, S, SW, W, NW, meaning north, northeast, east, southeast, south, southwest, west, and northwest, respectively.

No two distinct launchers share the same coordinates, and for every $i$, $x_i$, $y_i$, and $c_i$ are integers.

Print the minimum cost on the first line.

On the second line, print the indices of the launchers the marble passed through, including launcher $s$ and launcher $e$. If there are multiple routes that achieve the minimum cost, print any of them.

If it is impossible to reach launcher $e$, print $-1$ on the first line and terminate.

East is the direction in which the $x$-coordinate increases, and north is the direction in which the $y$-coordinate increases.