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 bisect
import heapq
import sys


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def calc_v(D, f, i):
    p, n, c = V(f), V(f), V(f)
    for d, P in D.items():
        for pp in P:
            if d == ("R" if i == 0 else "U"):
                p.ud(pp[i])
            elif d == ("L" if i == 0 else "D"):
                n.ud(pp[i])
            else:
                c.ud(pp[i])

    p = p.get()
    n = n.get()
    c = c.get()
    return p, n, c, f


def calc_e(p, n, c, f):
    if p is None:
        if c is None or n is None:
            return []
        else:
            return [n - c]

    if n is None:
        if c is None:
            return []
        else:
            return [c - p]

    t = (n - p) / 2
    if c is None:
        return [t]

    return [t, c - p, n - c]


def calc(t, L):
    res = V(L[3])
    if L[0] is not None:
        res.ud(L[0] + t)

    if L[1] is not None:
        res.ud(L[1] - t)

    if L[2] is not None:
        res.ud(L[2])

    return res.get()


def main():
    N = int(input())
    D = {
        "R": [],
        "L": [],
        "U": [],
        "D": [],
    }

    for _ in range(N):
        x, y, d = input().split()
        x = int(x)
        y = int(y)
        D[d].append((x, y))

    VV = []
    VV.append(calc_v(D, max, 0))
    VV.append(calc_v(D, min, 0))
    VV.append(calc_v(D, max, 1))
    VV.append(calc_v(D, min, 1))

    E = {0}
    for e in [calc_e(*v) for v in VV]:
        for t in e:
            E.add(t)

    res = V(min)
    for t in E:
        if t < 0:
            continue
        res.ud((calc(t, VV[0]) - calc(t, VV[1])) * (calc(t, VV[2]) - calc(t, VV[3])))
    print(res)


if __name__ == "__main__":
    main()