题目描述

在二维平面上有$N$个点。第个点的初始坐标为$(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$

接下来一共$N$行,形如$x_i,y_i,d_i$的形式

输出

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

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

2
0 3 D
3 0 L

0

样例解释

三秒后，两个点将会在原点相遇。题目所求的值在那一刻为 0。

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

97.5

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

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