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.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();

		int[] x = new int[n];
		int[] y = new int[n];
		char[] d = new char[n];
		for (int i = 0; i < n; i++) {
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			d[i] = sc.next().toCharArray()[0];
		}

		for (int i = 0; i < n; i++) {
			if (d[i] == 'R') {
				maxy = Math.max(maxy, y[i]);
				miny = Math.min(miny, y[i]);
				maxxr = Math.max(maxxr, x[i]);
				minxr = Math.min(minxr, x[i]);
			} else if (d[i] == 'L') {
				maxy = Math.max(maxy, y[i]);
				miny = Math.min(miny, y[i]);
				maxxl = Math.max(maxxl, x[i]);
				minxl = Math.min(minxl, x[i]);
			} else if (d[i] == 'U') {
				maxx = Math.max(maxx, x[i]);
				minx = Math.min(minx, x[i]);
				maxyu = Math.max(maxyu, y[i]);
				minyu = Math.min(minyu, y[i]);
			} else if (d[i] == 'D') {
				maxx = Math.max(maxx, x[i]);
				minx = Math.min(minx, x[i]);
				maxyd = Math.max(maxyd, y[i]);
				minyd = Math.min(minyd, y[i]);
			}
		}

		List<Integer> list = new ArrayList<>();
		list.add(0);
		list.add((maxx - maxxr) * 2);
		list.add((minx - maxxr) * 2);
		list.add((maxx - minxr) * 2);
		list.add((minx - minxr) * 2);
		list.add((maxxl - maxx) * 2);
		list.add((maxxl - minx) * 2);
		list.add((minxl - maxx) * 2);
		list.add((minxl - minx) * 2);
		list.add(maxxl - maxxr);
		list.add(maxxl - minxr);
		list.add(minxl - maxxr);
		list.add(minxl - minxr);
		list.add((maxy - maxyu) * 2);
		list.add((miny - maxyu) * 2);
		list.add((maxy - minyu) * 2);
		list.add((miny - minyu) * 2);
		list.add((maxyd - maxy) * 2);
		list.add((maxyd - miny) * 2);
		list.add((minyd - maxy) * 2);
		list.add((minyd - miny) * 2);
		list.add(maxyd - maxyu);
		list.add(maxyd - minyu);
		list.add(minyd - maxyu);
		list.add(minyd - minyu);

		long min = Long.MAX_VALUE;
		for (int i : list) {
			if (i < 0 || i > 1_000_000_000) {
				continue;
			}
			long tmp = (fmaxx(i) - fminx(i)) * (fmaxy(i) - fminy(i));
			min = Math.min(min, tmp);
		}
		
		pr.printf("%.10f%n", (double)min / 4);
	}
	
	private static long fmaxx(int i) {
		long max = 2L * maxx;
		max = Math.max(max, 2L * maxxl - i);
		max = Math.max(max, 2L * maxxr + i);
		
		return max;
	}

	private static long fminx(int i) {
		long min = 2L * minx;
		min = Math.min(min, 2L * minxl - i);
		min = Math.min(min, 2L * minxr + i);
		
		return min;
	}

	private static long fmaxy(int i) {
		long max = 2L * maxy;
		max = Math.max(max, 2L * maxyd - i);
		max = Math.max(max, 2L * maxyu + i);
		
		return max;
	}

	private static long fminy(int i) {
		long min = 2L * miny;
		min = Math.min(min, 2L * minyd - i);
		min = Math.min(min, 2L * minyu + i);
		
		return min;
	}

	static final int INF = Integer.MAX_VALUE;

	private static int maxx = -INF;
	private static int minx = INF;
	private static int maxxr = -INF;
	private static int minxr = INF;
	private static int maxxl = -INF;
	private static int minxl = INF;
	private static int maxy = -INF;
	private static int miny = INF;
	private static int maxyu = -INF;
	private static int minyu = INF;
	private static int maxyd = -INF;
	private static int minyd = INF;

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);
			
		solve();
			
		pr.close();
		sc.close();
	}

	static class Scanner {
		BufferedReader br;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		private boolean isPrintable(int ch) {
			return ch >= '!' && ch <= '~';
		}

		private boolean isCRLF(int ch) {
			return ch == '\n' || ch == '\r' || ch == -1;
		}

		private int nextPrintable() {
			try {
				int ch;
				while (!isPrintable(ch = br.read())) {
					if (ch == -1) {
						throw new NoSuchElementException();
					}
				}

				return ch;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		String next() {
			try {
				int ch = nextPrintable();
				StringBuilder sb = new StringBuilder();
				do {
					sb.appendCodePoint(ch);
				} while (isPrintable(ch = br.read()));

				return sb.toString();
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		int nextInt() {
			try {
				// parseInt from Integer.parseInt()
				boolean negative = false;
				int res = 0;
				int limit = -Integer.MAX_VALUE;
				int radix = 10;

				int fc = nextPrintable();
				if (fc < '0') {
					if (fc == '-') {
						negative = true;
						limit = Integer.MIN_VALUE;
					} else if (fc != '+') {
						throw new NumberFormatException();
					}
					fc = br.read();
				}
				int multmin = limit / radix;

				int ch = fc;
				do {
					int digit = ch - '0';
					if (digit < 0 || digit >= radix) {
						throw new NumberFormatException();
					}
					if (res < multmin) {
						throw new NumberFormatException();
					}
					res *= radix;
					if (res < limit + digit) {
						throw new NumberFormatException();
					}
					res -= digit;

				} while (isPrintable(ch = br.read()));

				return negative ? res : -res;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		long nextLong() {
			try {
				// parseLong from Long.parseLong()
				boolean negative = false;
				long res = 0;
				long limit = -Long.MAX_VALUE;
				int radix = 10;

				int fc = nextPrintable();
				if (fc < '0') {
					if (fc == '-') {
						negative = true;
						limit = Long.MIN_VALUE;
					} else if (fc != '+') {
						throw new NumberFormatException();
					}
					fc = br.read();
				}
				long multmin = limit / radix;

				int ch = fc;
				do {
					int digit = ch - '0';
					if (digit < 0 || digit >= radix) {
						throw new NumberFormatException();
					}
					if (res < multmin) {
						throw new NumberFormatException();
					}
					res *= radix;
					if (res < limit + digit) {
						throw new NumberFormatException();
					}
					res -= digit;

				} while (isPrintable(ch = br.read()));

				return negative ? res : -res;
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}

		float nextFloat() {
			return Float.parseFloat(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			try {
				int ch;
				while (isCRLF(ch = br.read())) {
					if (ch == -1) {
						throw new NoSuchElementException();
					}
				}
				StringBuilder sb = new StringBuilder();
				do {
					sb.appendCodePoint(ch);
				} while (!isCRLF(ch = br.read()));

				return sb.toString();
			} catch (IOException e) {
				throw new NoSuchElementException();
			}
		}
		
		int[] nextIntArray(int n) {
			int[] ret = new int[n];
			for (int i = 0; i < n; i++) {
				ret[i] = sc.nextInt();
			}
			
			return ret;
		}

		int[][] nextIntArrays(int n, int m) {
			int[][] ret = new int[m][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					ret[j][i] = sc.nextInt();
				}
			}
			
			return ret;
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new NoSuchElementException();
			}
		}
	}

	static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
		
		void printInts(int... a) {
			StringBuilder sb = new StringBuilder(32);
			for (int i = 0, size = a.length; i < size; i++) {
				if (i > 0) {
					sb.append(' ');
				}
				sb.append(a[i]);
			}

			println(sb);
		}
		
		void printLongs(long... a) {
			StringBuilder sb = new StringBuilder(64);
			for (int i = 0, size = a.length; i < size; i++) {
				if (i > 0) {
					sb.append(' ');
				}
				sb.append(a[i]);
			}

			println(sb);
		}
		
		void printStrings(String... a) {
			StringBuilder sb = new StringBuilder(32);
			for (int i = 0, size = a.length; i < size; i++) {
				if (i > 0) {
					sb.append(' ');
				}
				sb.append(a[i]);
			}

			println(sb);
		}
	}
}