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 itertools

def enum(a):
    t = [0]
    for a1, a2 in itertools.combinations(a, 2):
        t.append(a1[0]-a2[0])
        t.append(a2[0]-a1[0])
        t.append((a1[0]-a2[0])/2)
        t.append((a2[0]-a1[0])/2)
    return t

def calcWidth(l, t):
    x_min = x_max = l[0][0] + l[0][1] * t
    for item in l:
        x_min = min(x_min, item[0] + item[1] * t)
        x_max = max(x_max, item[0] + item[1] * t)
    return x_max - x_min

def calc(x_trip, y_trip, t):
    if t < 0:
        return calcWidth(x_trip, 0) * calcWidth(y_trip, 0)
    return calcWidth(x_trip, t) * calcWidth(y_trip, t)

n = int(input())
x_r, x_n, x_l = [], [], []
y_u, y_n, y_d = [], [], []
for _ in range(n):
    x, y, d = input().strip().split()
    x, y = int(x), int(y)
    if d == "R":
        x_r.append(x)
    elif d == "L":
        x_l.append(x)
    else:
        x_n.append(x)

    if d == "U":
        y_u.append(y)
    elif d == "D":
        y_d.append(y)
    else:
        y_n.append(y)

x_r.sort()
x_n.sort()
x_l.sort()
y_u.sort()
y_n.sort()
y_d.sort()

def ht(x, d):
    if len(x) > 0:
        return [(x[0], d), (x[-1], d)]
    return []
x_list = ht(x_r, 1) + ht(x_n, 0) + ht(x_l, -1)
y_list = ht(y_u, 1) + ht(y_n, 0) + ht(y_d, -1)
t = enum(x_list + y_list)

ans = calc(x_list, y_list, 0)
for t1 in t:
    if t1 < 0:
        continue
    wx = calcWidth(x_list, t1)
    wy = calcWidth(y_list, t1)
    ans = min(ans, calc(x_list, y_list, t1))
    ans = min(ans, calc(x_list, y_list, t1 + (wx-wy)/2))
    ans = min(ans, calc(x_list, y_list, t1 + (wy-wx)/2))
    ans = min(ans, calc(x_list, y_list, t1 + (wx*2-wy)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wx-wy*2)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wy*2-wx)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wy-wx*2)/4))
    ans = min(ans, calc(x_list, y_list, t1 + (wx*2-wy*2)/8))
    ans = min(ans, calc(x_list, y_list, t1 + (wy*2-wx*2)/8))
print(ans)