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:
def timecalc(p1,p2,speed):
    h1,h2= p1
    l1,l2= p2
    return ((h1-l1)/speed,(h1-l2)/speed,(h2-l1)/speed,(h2-l2)/speed)

n=int(input())
ans=2**62
X = []
Y = []
U = []
D = []
L = []
R = []

for i in range(n):
    xin = input().split()
    x,y,dir = int(xin[0]),int(xin[1]),xin[2]
    if dir=='U':
        X.append(x)
        U.append(y)
    elif dir=='D':
        X.append(x)
        D.append(y)
    elif dir=='L':
        Y.append(y)
        L.append(x)
    else:
        Y.append(y)
        R.append(x)
if n==1:
    print(0)
    exit(0)

if X:
    X = [max(X),min(X)]
if Y:
    Y = [max(Y),min(Y)]
if U:
    U = [max(U),min(U)]
if D:
    D = [max(D),min(D)]
if L:
    L = [max(L),min(L)]
if R:
    R = [max(R),min(R)]
T = []

if X and R:
    T.extend( [i for i in timecalc(X,R,1) if i>0] )
if L and X:
    T.extend( [i for i in timecalc(L,X,1) if i>0] )
if Y and U:
    T.extend( [i for i in timecalc(Y,U,1) if i>0] )
if D and Y:
    T.extend( [i for i in timecalc(D,Y,1) if i>0] )
if L and R:
    T.extend( [i for i in timecalc(L,R,2) if i>0] )
if D and U:
    T.extend( [i for i in timecalc(D,U,2) if i>0] )

T = list(set(T))
T.append(0)

for i in T:
    xmax = -10**9
    ymax = -10**9
    xmin = 10**9
    ymin = 10**9
    if X:
        xmax = max(xmax,X[0])
        xmin = min(xmin,X[1])
    if Y:
        ymax = max(ymax,Y[0])
        ymin = min(ymin,Y[1])
    if U:
        ymax = max(ymax,U[0]+i)
        ymin = min(ymin,U[1]+i)
    if D:
        ymax = max(ymax,D[0]-i)
        ymin = min(ymin,D[1]-i)
    if L:
        xmax = max(xmax,L[0]-i)
        xmin = min(xmin,L[1]-i)
    if R:
        xmax = max(xmax,R[0]+i)
        xmin = min(xmin,R[1]+i)
    
    ans = min(ans,((xmax-xmin)*(ymax-ymin)))

print(ans)