Mirko 在阁楼里找到了一个木板和 $N$ 个钉子。Mirko 尽可能快地把这些钉子钉进了木板里。木板可以建模为一个平面直角坐标系，钉子则是其中的点。没有任意两个钉子具有相同的 $x$ 坐标或相同的 $y$ 坐标。

为了继续寻找乐趣，Mirko 拿了他姐姐的弹性发圈，把它撑开套在所有的钉子上，然后松手。自然地，发圈会紧紧地绷在最外圈的钉子周围。

只要木板上还有至少三个钉子，Mirko 就会重复以下步骤：

1. 写下发圈所围成图形的面积。
2. 选择木板上最左侧、最右侧、最上方或最下方的钉子。
3. 从木板上拔掉选中的钉子；发圈会重新紧绷在剩余的钉子周围。

如果我们知道 Mirko 在每一步中选择的钉子，请编写一个程序，计算他在每一步中写下的面积。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 300\,000$)，表示钉子的数量。

接下来的 $N$ 行，每行包含两个由空格隔开的整数，表示一个钉子的坐标。所有坐标都在 $1$ 到 $1\,000\,000\,000$ 之间。没有任意两个钉子会共享相同的 $x$ 或 $y$ 坐标。

下一行包含 $N-2$ 个字符，字符为 'L'、'R'、'U' 或 'D'。这些字母按顺序表示 Mirko 选择的钉子：

• 'L' 表示最左侧的钉子（$x$ 坐标最小），
• 'R' 表示最右侧的钉子（$x$ 坐标最大），
• 'U' 表示最上方的钉子（$y$ 坐标最大），
• 'D' 表示最下方的钉子（$y$ 坐标最小）。

输出格式

输出 $N-2$ 个数，每行一个。这些数依次为 Mirko 写下的面积。输出的数值保留一位小数。

数据范围

在占总分 50% 的测试数据中，$N$ 将小于 $1000$。

样例

输入 1

5
1 4
2 2
4 1
3 5
5 3
LUR

输出 1

9.0
6.5
2.5

输入 2

8
1 6
2 4
3 1
4 2
5 7
6 5
7 9
8 3
URDLUU

输出 2

34.0
24.0
16.5
14.0
9.5
5.0

说明

下图展示了第二个样例中 6 个步骤中每一步之前的状态。