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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    if N==1:
        print(0)
        exit()
    inf=10**10
    #xmax,xmin,ymax,yminそれぞれの時間変化のグラフを見ると上か下に凸ぽい，3本以下の直線で作れる
    #左右上下の値候補，-t,定数,tの時の定数部分
    #xminやxmaxなどが入れ替わるタイミングぐらいでしか最小を取り得ない
    
    X=[0]*N
    Y=[0]*N
    D=[0]*N
    
    for i in range(N):
        xyd=input().split()
        X[i]=int(xyd[0])
        Y[i]=int(xyd[1])
        D[i]=xyd[2]
        
    # x方向に-1,0,1の速度で動くそれぞれの最大値と最小値を求めるか，こいつらが交わるタイミングが大事
    # X方向か，Y方向か
    def calc_ts(S,XX):
        if S=="X":
            L="L"
            R="R"
        else:
            L="D"#min
            R="U"#max
        xmin=[inf,inf,inf]
        xmax=[-inf,-inf,-inf]
        for i in range(N):
            x=XX[i]
            d=D[i]
            if d==L:
                xmin[0]=min(xmin[0],x)
                xmax[0]=max(xmax[0],x)
            elif d==R:
                xmin[2]=min(xmin[2],x)
                xmax[2]=max(xmax[2],x)
            else:
                xmin[1]=min(xmin[1],x)
                xmax[1]=max(xmax[1],x)
        ts=[]
        
        t=xmin[0]-xmin[1]
        if t>0:
            ts.append(t)
            
        t=xmin[0]-xmin[2]
        if t>0:
            ts.append(t/2)
            
        t=xmin[1]-xmin[2]
        if t>0:
            ts.append(t)

        t=xmax[0]-xmax[1]
        if t>0:
            ts.append(t)
            
        t=xmax[0]-xmax[2]
        if t>0:
            ts.append(t/2)
            
        t=xmax[1]-xmax[2]
        if t>0:
            ts.append(t)
            
        return ts
    
    ts_all=[0]
    ts_all+=calc_ts("X",X)
    ts_all+=calc_ts("Y",Y)
    
    #t秒後の面積
    def calc(t):
        xmin=inf
        xmax=-inf
        ymin=inf
        ymax=-inf
        
        for i in range(N):
            x=X[i]
            y=Y[i]
            d=D[i]
            
            if d=="L":
                xmin=min(xmin,x-t)
                xmax=max(xmax,x-t)
                ymin=min(ymin,y)
                ymax=max(ymax,y)
            elif d=="R":
                xmin=min(xmin,x+t)
                xmax=max(xmax,x+t)
                ymin=min(ymin,y)
                ymax=max(ymax,y)
            elif d=="U":
                xmin=min(xmin,x)
                xmax=max(xmax,x)
                ymin=min(ymin,y+t)
                ymax=max(ymax,y+t)
            else:
                xmin=min(xmin,x)
                xmax=max(xmax,x)
                ymin=min(ymin,y-t)
                ymax=max(ymax,y-t)
        return (xmax-xmin)*(ymax-ymin)
    
    ans=inf**2
    for t in ts_all:
        temp=calc(t)
        ans=min(ans,temp)
        
    print(ans)
    

        
    


main()