У Васи есть $$$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$$$ отрезка, которые не являются соседними, не имеют общих точек.
• она будет извилистой.

У Васи есть строка $$$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$$$. Найдите перестановку $$$p_1, p_2, \ldots, p_n$$$ чисел от $$$1$$$ до $$$n$$$, такую что ломаная, которую нарисует Вася, будет удовлетворять двум заданным условиям.