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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author anand.oza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FMinimumBoundingBox solver = new FMinimumBoundingBox();
        solver.solve(1, in, out);
        out.close();
    }

    static class FMinimumBoundingBox {
        double[] permanentX;
        double[] leftX;
        double[] rightX;
        double[] permanentY;
        double[] upY;
        double[] downY;
        double[] all;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();

            permanentX = new double[]{Double.POSITIVE_INFINITY,
                                      Double.NEGATIVE_INFINITY};
            leftX = new double[]{Double.POSITIVE_INFINITY,
                                 Double.NEGATIVE_INFINITY};
            rightX = new double[]{Double.POSITIVE_INFINITY,
                                  Double.NEGATIVE_INFINITY};
            permanentY = new double[]{Double.POSITIVE_INFINITY,
                                      Double.NEGATIVE_INFINITY};
            upY = new double[]{Double.POSITIVE_INFINITY,
                               Double.NEGATIVE_INFINITY};
            downY = new double[]{Double.POSITIVE_INFINITY,
                                 Double.NEGATIVE_INFINITY};
            all = new double[]{Double.POSITIVE_INFINITY,
                               Double.NEGATIVE_INFINITY};

            for (int i = 0; i < n; i++) {
                long x = in.nextInt(), y = in.nextInt();
                char d = in.next().charAt(0);
                apply(all, x);
                apply(all, y);
                switch (d) {
                    case 'L':
                        apply(permanentY, y);
                        apply(leftX, x);
                        break;
                    case 'R':
                        apply(permanentY, y);
                        apply(rightX, x);
                        break;
                    case 'U':
                        apply(permanentX, x);
                        apply(upY, y);
                        break;
                    case 'D':
                        apply(permanentX, x);
                        apply(downY, y);
                        break;
                }
            }

//        System.out.println(Arrays.toString(permanentX));
//        System.out.println(Arrays.toString(leftX));
//        System.out.println(Arrays.toString(rightX));
//        System.out.println(Arrays.toString(permanentY));
//        System.out.println(Arrays.toString(upY));
//        System.out.println(Arrays.toString(downY));

            out.format("%f%n", solveWrongWithZero());
        }

        public double solveWrongWithZero() {
            double answer = score(0);
            for (int i = 0; i <= 1; i++) {
                double[] t = new double[]{leftX[i] - permanentX[i],
                                          permanentX[i] - rightX[i],
                                          (leftX[i] - rightX[i]) / 2,
                                          downY[i] - permanentY[i],
                                          permanentY[i] - upY[i],
                                          (downY[i] - upY[i]) / 2};

                for (double time : t) {
                    if (time < 0 || !Double.isFinite(time))
                        continue;

                    double score = score(time);
                    if (!Double.isFinite(score))
                        continue;
                    answer = Math.min(answer, score(time));
                }
            }

            return answer;
        }

        double score(double t) {
            double xMin = Double.POSITIVE_INFINITY;
            xMin = Math.min(xMin, permanentX[0]);
            xMin = Math.min(xMin, leftX[0] - t);
            xMin = Math.min(xMin, rightX[0] + t);

            double xMax = Double.NEGATIVE_INFINITY;
            xMax = Math.max(xMax, permanentX[1]);
            xMax = Math.max(xMax, leftX[1] - t);
            xMax = Math.max(xMax, rightX[1] + t);

            double yMin = Double.POSITIVE_INFINITY;
            yMin = Math.min(yMin, permanentY[0]);
            yMin = Math.min(yMin, downY[0] - t);
            yMin = Math.min(yMin, upY[0] + t);

            double yMax = Double.NEGATIVE_INFINITY;
            yMax = Math.max(yMax, permanentY[1]);
            yMax = Math.max(yMax, downY[1] - t);
            yMax = Math.max(yMax, upY[1] + t);

            return Math.abs((yMax - yMin) * (xMax - xMin));
        }

        static void apply(double[] coords, double input) {
            coords[0] = Math.min(coords[0], input);
            coords[1] = Math.max(coords[1], input);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}