구불구불한 경로

그림의 경로는 (4, 4)에서 출발해 (2, 5)로 간다. 여기서 오른쪽으로 꺾어 (1, 6)으로 가고, 다시 왼쪽으로 크게 꺾어 (5, 0)으로 간 다음, 한 번 더 왼쪽으로 꺾어 (4, 2)에서 끝난다. 왼쪽 회전을 L, 오른쪽 회전을 R로 적으면 이 경로의 회전 방향은 차례대로 RLL이다. 경로는 자기 자신과 교차하지 않는다. 선분이 만나는 곳은 경로를 잇는 점뿐이다.

이제 반대 문제를 푼다. 점 $N$개가 임의의 순서로 주어진다. 모든 점을 정확히 한 번씩 지나면서 경로가 자기 자신과 교차하지 않고, 회전 방향을 이어 적은 문자열이 주어진 문자열과 같아지는 순서를 찾아야 한다. 예를 들어 점 (2, 5), (1, 6), (4, 4), (5, 0), (4, 2)가 이 순서로 주어지고 회전 문자열이 RLL이면, 순서 3 1 2 4 5가 그림의 경로를 나타낸다. 세 번째 점 (4, 4)에서 시작해 첫 번째, 두 번째, 네 번째, 다섯 번째 점을 차례로 지난다.

연속한 세 점 $a$, $b$, $c$에 대해 $b$에서의 회전 방향은 외적 $(b - a) \times (c - b)$의 부호로 정한다. 부호가 양수면 L, 음수면 R이다. 한 직선 위에 놓인 세 점은 입력에 나오지 않으므로 부호가 0이 되는 일은 없다.

같은 문자열을 만족하는 순서는 보통 여러 개다. 위의 3 1 2 4 5도 그중 하나이고, 아래 출력 규칙이 고르는 답과 다를 수 있다.

첫째 줄에 점의 개수 $N$이 주어진다 ($3 \le N \le 50$). 다음 $N$개 줄에 각 점의 좌표 $x_i$와 $y_i$가 공백으로 구분되어 주어진다 ($0 \le x_i, y_i \le 1000$). 모든 점은 서로 다르고, 한 직선 위에 놓인 세 점은 없다. 마지막 줄에 L과 R로만 이루어진 길이 $N - 2$의 문자열이 주어진다.

다음 절차가 만드는 순열을 한 줄에 출력한다. 점에는 입력에 주어진 순서대로 1부터 $N$까지 번호를 붙이고, 수 사이는 공백 하나로 구분한다.

1. $y$좌표가 가장 작은 점에서 시작한다. 그런 점이 여럿이면 그중 $x$좌표가 가장 작은 점에서 시작한다.
2. $k = 1$부터 $N - 2$까지 다음을 반복한다. 지금까지 만든 경로의 마지막 점을 $p$, 회전 문자열의 $k$번째 문자를 $c$라고 하자. 아직 쓰지 않은 점 중에서 다음 조건을 만족하는 점 $q$를 고른다. $c$가 L이면 $q$를 제외한 나머지 미사용 점이 모두 $p$에서 $q$로 향하는 유향 직선의 왼쪽에 있어야 하고, $c$가 R이면 모두 오른쪽에 있어야 한다. 이런 $q$는 항상 정확히 하나 있다. 고른 $q$를 경로 끝에 붙인다.
3. 마지막으로 남은 점 하나를 경로 끝에 붙인다.

이 절차로 만든 경로는 자기 자신과 교차하지 않고, 회전 방향 문자열도 주어진 문자열과 같다.