题目描述

There are $N$ points in a two-dimensional plane. The initial coordinates of the $i$-th point are $(x_i, y_i)$. Now, each point starts moving at a speed of 1 per second, in a direction parallel to the $x$- or $y$- axis. You are given a character $d_i$ that represents the specific direction in which the $i$-th point moves, as follows:

• If $d_i =$ R, the $i$-th point moves in the positive $x$ direction;
• If $d_i =$ L, the $i$-th point moves in the negative $x$ direction;
• If $d_i =$ U, the $i$-th point moves in the positive $y$ direction;
• If $d_i =$ D, the $i$-th point moves in the negative $y$ direction.

You can stop all the points at some moment of your choice after they start moving (including the moment they start moving). Then, let $x_{max}$ and $x_{min}$ be the maximum and minimum among the $x$-coordinates of the $N$ points, respectively. Similarly, let $y_{max}$ and $y_{min}$ be the maximum and minimum among the $y$-coordinates of the $N$ points, respectively.

Find the minimum possible value of $(x_{max} - x_{min}) \times (y_{max} - y_{min})$ and print it.

二维平面上有 $N$ 个点。第 $i$ 个点的初始坐标为 $(x_i, y_i)$ 。现在，每个点开始以每秒 1 的速度沿平行于 $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_{max}$ 和 $x_{min}$ 分别成为 $N$ 个点的 $x$ 个坐标中的最大值和最小值。同样，设 $y_{max}$ 和 $y_{min}$ 分别是 $N$ 个点的 $y$ 个坐标中的最大值和最小值。

求出 $(x_{max} - x_{min}) \times (y_{max} - y_{min})$ 的最小值并打印出来。

输入格式

输入内容按以下格式标准输入：

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

输出格式

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

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

样例 #1

样例输入 #1

2
0 3 D
3 0 L

样例输出 #1

0

样例 #2

样例输入 #2

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

样例输出 #2

97.5

样例 #3

样例输入 #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

说明

数据规模与约定

• $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。

样例 $1$ 解释

三秒后，两点在原点相遇。此时的值为 $0$ 。

样例 $2$ 解释

答案可能不是整数。