问题描述

在二维平面上有 $N$ 个点。第 $i$ 个点的初始坐标为 $(x_i, y_i)$。现在，每个点以单位速度开始运动，沿着 $x$ 轴或 $y$ 轴的方向移动。给定一个字符 $d_i$ 表示第 $i$ 个点移动的具体方向，如下所示：

• 如果 $d_i =$ R，第 $i$ 个点朝正 $x$ 方向移动；
• 如果 $d_i =$ L，第 $i$ 个点朝负 $x$ 方向移动；
• 如果 $d_i =$ U，第 $i$ 个点朝正 $y$ 方向移动；
• 如果 $d_i =$ D，第 $i$ 个点朝负 $y$ 方向移动。

你可以在它们开始移动之后的某个时刻停止所有点。然后，令 $x_{\text{max}}$ 和 $x_{\text{min}}$ 分别为 $N$ 个点的 $x$ 坐标的最大值和最小值，$y_{\text{max}}$ 和 $y_{\text{min}}$ 分别为 $N$ 个点的 $y$ 坐标的最大值和最小值。

找到 $(x_{\text{max}} - x_{\text{min}}) \times (y_{\text{max}} - y_{\text{min}})$ 的最小可能值并打印出来。

约束条件

• $1 \leq N \leq 10^5$
• $-10^8 \leq x_i, y_i \leq 10^8$
• $x_i$ 和 $y_i$ 都是整数。
• $d_i$ 是 R、L、U 或 D。

输入

输入以以下格式从标准输入中给出：

$N$ $x_1$ $y_1$ $d_1$ $x_2$ $y_2$ $d_2$ ... $x_N$ $y_N$ $d_N$

输出

打印 $(x_{\text{max}} - x_{\text{min}}) \times (y_{\text{max}} - y_{\text{min}})$ 的最小可能值。

当与测试用例的输出的绝对或相对误差不超过 $10^{-9}$ 时，输出将被视为正确。

示例输入 1

2
0 3 D
3 0 L

示例输出 1

0

三秒后，两个点将在原点相遇。此时问题所求的值将为 $0$。

示例输入 2

5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R

示例输出 2

97.5

答案可能不是整数。

示例输入 3

20
6 -10 R
-4 -9 U
9 6 D
-3 -2 R
0 7 D
4 5 D
10 -10 U
-1 -8 U
10 -6 D
8 -5 U
6 4 D
0 3 D
7 9 R
9 -4 R
3 10 D
1 9 U
1 -6 U
9 -8 R
6 7 D
7 -3 D

示例输出 3

273

请务必打印结果，并允许与测试用例输出的绝对或相对误差不超过 $10^{-9}$。