Windy Path

The path in the figure starts at (4, 4) and goes to (2, 5). There it turns right toward (1, 6), then makes a sharp left to (5, 0), then one more left to (4, 2). Writing L for a left turn and R for a right turn, the turn directions along this path are RLL. The path does not cross itself. The only place where two segments meet is a point of the path.

Now solve the reverse problem. $N$ points are given in an arbitrary order. Find an order that visits every point exactly once so that the path does not cross itself and the string of its turn directions equals a given string. For example, with the points (2, 5), (1, 6), (4, 4), (5, 0), (4, 2) given in that order and the turn string RLL, the order 3 1 2 4 5 traces the path in the figure. It starts at the third point (4, 4), then takes the first, second, fourth, and fifth points.

For three consecutive points $a$, $b$, $c$, the turn at $b$ is decided by the sign of the cross product $(b - a) \times (c - b)$. A positive sign is L and a negative sign is R. The input never contains three points on one line, so the sign is never 0.

Several orders usually satisfy the same string. The order 3 1 2 4 5 above is one of them, and it can differ from the answer that the output rule below selects.

The first line contains the number of points $N$ ($3 \le N \le 50$). Each of the next $N$ lines contains the coordinates $x_i$ and $y_i$ of one point, separated by a space ($0 \le x_i, y_i \le 1000$). The points are distinct and no three of them lie on one line. The last line contains a string of length $N - 2$ made only of the characters L and R.

Print, on one line, the permutation that the following procedure builds. The points are numbered 1 to $N$ in the order they are given, and the numbers are separated by single spaces.

1. Start at the point with the smallest $y$ coordinate. If several points share that $y$, start at the one with the smallest $x$ coordinate among them.
2. Repeat the following for $k = 1$ to $N - 2$. Let $p$ be the last point of the path built so far and let $c$ be the $k$-th character of the turn string. Among the unused points, take the point $q$ with this property. If $c$ is L, every other unused point lies strictly to the left of the directed line from $p$ to $q$. If $c$ is R, every other unused point lies strictly to the right. Exactly one such $q$ exists. Append $q$ to the path.
3. Append the single point that is still unused.

The path built this way does not cross itself, and its turn directions equal the given string.