Problem: 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.

Constraints

* 1 \leq N \leq 10^5
* -10^8 \leq x_i,\ y_i \leq 10^8
* x_i and y_i are integers.
* d_i is `R`, `L`, `U`, or `D`.

Input

Input is given from Standard Input in the following format:


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


Output

Print the minimum possible value of (x_{max} - x_{min}) \times (y_{max} - y_{min}).

The output will be considered correct when its absolute or relative error from the judge's output is at most 10^{-9}.

Examples

Input

2
0 3 D
3 0 L


Output

0


Input

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


Output

97.5


Input

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


Output

273

Solution (in PYTHON3):

Solution:
import sys
input = sys.stdin.readline

INF = 10**18

N = int(input())
D = []
U = []
L = []
R = []
UD = []
LR = []
for _ in range(N):
    str_x, str_y, d = map(str, input().rstrip().split())
    x = int(str_x)
    y = int(str_y)
    if d == "U":
        U.append(y)
        UD.append(x)
    elif d == "D":
        D.append(y)
        UD.append(x)
    elif d == "L":
        L.append(x)
        LR.append(y)
    else:
        R.append(x)
        LR.append(y)

UD.sort()
LR.sort()
U.sort()
D.sort()
L.sort()
R.sort()

T = [0]
if L and R:
    T.append((L[0]-R[0])/2)
    T.append((L[-1]-R[-1])/2)
if L and UD:
    T.append(L[0]-UD[0])
    T.append(L[-1]-UD[-1])
if R and UD:
    T.append(UD[0]-R[0])
    T.append(UD[-1]-R[-1])
if U and D:
    T.append((D[0]-U[0])/2)
    T.append((D[-1]-U[-1])/2)
if U and LR:
    T.append(-U[0]+LR[0])
    T.append(-U[-1]+LR[-1])
if D and LR:
    T.append(-LR[0]+D[0])
    T.append(-LR[-1]+D[-1])

ans = INF
for t in T:
    if t < 0: continue
    l = INF
    r = -INF
    d = INF
    u = -INF
    if L:
        l = min(l, L[0]-t)
        r = max(r, L[-1]-t)
    if R:
        l = min(l, R[0]+t)
        r = max(r, R[-1]+t)
    if U:
        d = min(d, U[0]+t)
        u = max(u, U[-1]+t)
    if D:
        d = min(d, D[0]-t)
        u = max(u, D[-1]-t)
    if LR:
        d = min(d, LR[0])
        u = max(u, LR[-1])
    if UD:
        l = min(l, UD[0])
        r = max(r, UD[-1])
    ans = min(ans, (r-l)*(u-d))

print(ans)