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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
	static double pnone = Integer.MAX_VALUE;
	static double mnone = Integer.MIN_VALUE;
	static double rmin = pnone;
	static double rmax = mnone;
	static double lmin = pnone;
	static double lmax = mnone;
	static double xmin = pnone;
	static double xmax = mnone;
	static double umin = pnone;
	static double umax = mnone;
	static double dmin = pnone;
	static double dmax = mnone;
	static double ymin = pnone;
	static double ymax = mnone;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Ten[] arr = new Ten[n];
		for (int i = 0; i < n; i++) {
			Ten t = new Ten(br.readLine());
			arr[i] = t;
		}
		br.close();

		for (int i = 0; i < n; i++) {
			Ten t = arr[i];
			if (t.dx == 1) {
				rmin = Math.min(rmin, t.x);
				rmax = Math.max(rmax, t.x);
			} else if (t.dx == -1) {
				lmin = Math.min(lmin, t.x);
				lmax = Math.max(lmax, t.x);
			} else {
				xmin = Math.min(xmin, t.x);
				xmax = Math.max(xmax, t.x);
			}
		}

		for (int i = 0; i < n; i++) {
			Ten t = arr[i];
			if (t.dy == 1) {
				umin = Math.min(umin, t.y);
				umax = Math.max(umax, t.y);
			} else if (t.dy == -1) {
				dmin = Math.min(dmin, t.y);
				dmax = Math.max(dmax, t.y);
			} else {
				ymin = Math.min(ymin, t.y);
				ymax = Math.max(ymax, t.y);
			}
		}

//		System.out.println("rmin: " + rmin);
//		System.out.println("rmax: " + rmax);
//		System.out.println("lmin: " + lmin);
//		System.out.println("lmax: " + lmax);
//		System.out.println("xmin: " + xmin);
//		System.out.println("xmax: " + xmax);
//		System.out.println("umin: " + umin);
//		System.out.println("umax: " + umax);
//		System.out.println("dmin: " + dmin);
//		System.out.println("dmax: " + dmax);
//		System.out.println("ymin: " + ymin);
//		System.out.println("ymax: " + ymax);

		Set<Double> set = new HashSet<Double>();
		set.add(0d);
		if (rmin < lmin) set.add((lmin - rmin) / 2);
		if (rmin < xmin) set.add(xmin - rmin);
		if (xmin < lmin) set.add(lmin - xmin);
		if (rmax < lmax) set.add((lmax - rmax) / 2);
		if (rmax < xmax) set.add(xmax - rmax);
		if (xmax < lmax) set.add(lmax - xmax);
		if (umin < dmin) set.add((dmin - umin) / 2);
		if (umin < ymin) set.add(ymin - umin);
		if (ymin < dmin) set.add(dmin - ymin);
		if (umax < dmax) set.add((dmax - umax) / 2);
		if (umax < ymax) set.add(ymax - umax);
		if (ymax < dmax) set.add(dmax - ymax);

		double ans = Double.MAX_VALUE;
		for (double t : set) {
			ans = Math.min(ans, calc(t));
		}
		System.out.println(ans);
	}

	static double calc(double t) {
		double xxmax = xmax;
		xxmax = Math.max(xxmax, lmax - t);
		xxmax = Math.max(xxmax, rmax + t);
		double xxmin = xmin;
		xxmin = Math.min(xxmin, lmin - t);
		xxmin = Math.min(xxmin, rmin + t);

		double yymax = ymax;
		yymax = Math.max(yymax, dmax - t);
		yymax = Math.max(yymax, umax + t);
		double yymin = ymin;
		yymin = Math.min(yymin, dmin - t);
		yymin = Math.min(yymin, umin + t);

		return (xxmax - xxmin) * (yymax - yymin);
	}

	static class Ten {
		double x, y;
		String d;
		int dx, dy;

		public Ten(String s) {
			String[] sa = s.split(" ");
			x = Long.parseLong(sa[0]);
			y = Long.parseLong(sa[1]);
			d = sa[2];
			if (d.equals("R")) {
				dx = 1;
			} else if (d.equals("L")) {
				dx = -1;
			} else if (d.equals("U")) {
				dy = 1;
			} else if (d.equals("D")) {
				dy = -1;
			}
		}
	}
}