Vasya 在平面上有 $$$n$$$ 个不同点 $$$A_1、A_2、\ldots A_n$$$。它们中没有三个位于同一行,他希望将它们按某种顺序放置 $$$A_{p_1}, A_{p_2}, \ldots, A_{p_n}$$$,其中 $$$p_1, p_2, \ldots, p_n$$$ - 从 $$$1$$$ 到 $$$n$$$ 的整数排列。
这样做之后,他将在这些点上绘制定向折线,并按所选顺序从每个点到下一个点绘制定向线段。因此,对于所有 $$$1 \leq i \leq n-1$$$,他将从点 $$$A_{p_i}$$$ 到点 $$$A_{p_{i+1}}$$$ 绘制定向线段。他想让这条折线满足$$$2$$$条件:
- 它将是非自相交的,因此任何不是邻居的 $$$2$$$ 线段没有公共点。
- 它将被缠绕。
Vasya 有一个字符串 $$$s$$$,由 $$$(n-2)$$$ 符号“L”或“R”组成。如果$$$i$$$向左转(如果$$$s_i = $$$“L”),则我们将其称为定向折线缠绕;如果$$$s_i = $$$“R”则向右转。更正式地说:第 $$$i$$$ 转弯将在点 $$$A_{p_{i+1}}$$$ 处,其中从点 $$$A_{p_i}$$$ 到点 $$$A_{p_{i+1}}$$$ 的定向线段更改为从点 $$$A_{p_{i+1}}$$$ 到点 $$$A_{p_{i+2}}$$$ 的定向线段。让我们定义向量 $$$\overrightarrow{v_1} = \overrightarrow{A_{p_i} A_{p_{i+1}}}$$$ 和 $$$\overrightarrow{v_2} = \overrightarrow{A_{p_{i+1}} A_{p_{i+2}}}$$$。然后,如果为了将向量 $$$\overrightarrow{v_1}$$$ 旋转尽可能小的角度,使其方向与向量 $$$\overrightarrow{v_2}$$$ 的方向一致,我们需要逆时针转动,那么我们说第 $$$i$$$ 转动是向左,否则是向右。为了更好地理解,请看这张图片和一些转弯示例:
这张图有左转
这张图有右转
给定平面上点 $$$A_1、A_2、\ldots A_n$$$ 的坐标和字符串 $$$s$$$。求 $$$1$$$ 到 $$$n$$$ 整数的排列 $$$p_1, p_2, \ldots, p_n$$$,使得 Vasya 绘制的折线满足两个必要条件。
输入
第一行包含一个整数 $$$n$$$ — 点数 ($$$3 \leq n \leq 2000$$$)。接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$,除以空间 - 平面上点 $$$A_i$$$ 的坐标 ($$$-10^9 \leq x_i, y_i \leq 10^9$$$)。最后一行包含一个字符串$$$s$$$,由符号“L”和“R”组成,长度为$$$(n-2)$$$。保证所有点都不同并且没有三个点位于同一条线上。
输出
如果满足的排列不存在,则打印 $$$-1$$$。在另一种情况下,打印 $$$n$$$ 数字 $$$p_1, p_2, \ldots, p_n$$$ - 找到的排列($$$1 \leq p_i \leq n$$$ 和所有 $$$p_1, p_2, \ldots, p_n$$$ 都是不同的)。如果存在多个解决方案,您可以找到任何一个。
示例
输入 #1
3 1 1 3 1 1 3 L
输出 #1
1 2 3
输入 #2
6 1 0 0 1 0 2 -1 0 -1 -1 2 1 RLLR
输出 #2
6 1 3 4 2 5
注意
这是$$$1$$$测试中带有折线的图片:
正如我们所见,这条折线是非自相交且蜿蜒的,因为拐点 $$$2$$$ 已离开。
这是$$$2$$$测试中带有折线的图片: