#1339. 摇摆路径

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: zxyoi

题目描述

在调查表上有这样一个问题:在执行总路线时你摇摆过吗?
拉宾诺维奇回答道:“我和总路线一起摇摆。”

平面直角坐标系 上有 个点,没有任何三个点在同一条直线上。

你从任意一个点开始,每次选择一个之前没有访问过的点,沿两点连线走过去,如此进行直到所有点都被访问过,按访问顺序写下这些点的标号,这样你就得到了一个长度为 的排列。

不难发现,由于没有三点共线,从第二条路径开始,与前一条路径相比方向必然转过了一个角度。

如果一次新的前进方向较原方向是逆时针转动一个不超过 的角度,我们称之为左转,否则称之为右转。

不难发现,总共有 条路径, 次转向。

现在,给出这些点在 中的坐标,以及一个长度为 仅由 构成的序列。

现在你需要给出一个点集的排列 ,满足:若 ,则 的方向相对于 的方向必须向左旋转(逆时针),若 同理,只不过旋转的方向需要改为向右(顺时针)。

输入格式

第一行一个整数 ,表示点的数量。

接下来 行,每行两个整数 表示点的坐标,保证没有任何三个点位于同一直线上。

最后一行一个长度为 的字符串,仅包含两种字符 ,含义如题目描述所示。

输出格式

一行 个整数表示你的答案。

保证给出的数据有解。

样例

样例输入

4
2 2
2 1
1 2
1 1
LR

样例输出

1 3 2 4

数据范围与提示