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

class Section{
    double min, max;
    public Section(double min, double max){
        this.min=min;
        this.max=max;
    }
    public Section(double elm){
        this(elm,elm);
    }
    public Section(){
        this(1e12, -1e12);
    }
    public void add(double elm){
        this.min = Math.min(this.min, elm);
        this.max = Math.max(this.max, elm);
    }
    public double minimum(){return min;}
    public double maximum(){return max;}
    public String toString(){
        return "["+min+", "+max+"]";
    }
}

public class Main {
    static double score(Section xStop, Section yStop, Section left, Section right, Section up, Section down, double time){
        double xMax = Math.max(xStop.maximum(), Math.max(left.maximum()-time, right.maximum()+time));
        double xMin = Math.min(xStop.minimum(), Math.min(left.minimum()-time, right.minimum()+time));
        double yMax = Math.max(yStop.maximum(), Math.max(up.maximum()+time, down.maximum()-time));
        double yMin = Math.min(yStop.minimum(), Math.min(up.minimum()+time, down.minimum()-time));
        return (xMax-xMin)*(yMax-yMin);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Section xStop = new Section();
        Section yStop = new Section();
        Section left = new Section();
        Section right = new Section();
        Section up = new Section();
        Section down = new Section();

        for(int n=0; n<N; n++){
            double x = sc.nextDouble();
            double y = sc.nextDouble();
            char d = sc.next().charAt(0);
            switch(d){
                case 'R':
                    right.add(x);
                    yStop.add(y);
                    break;
                case 'L':
                    left.add(x);
                    yStop.add(y);
                    break;
                case 'U':
                    up.add(y);
                    xStop.add(x);
                    break;
                case 'D':
                    down.add(y);
                    xStop.add(x);
                    break;
            }
        }

        for(double t=0; t<10; t+=0.1) score(xStop,yStop,left,right,up,down,t);

        double minTime = 0, maxTime = 1e12;
        for(int q=0; q<1000; q++){
            double early = (minTime*2+maxTime)/3;
            double late = (minTime+maxTime*2)/3;
            if(score(xStop,yStop,left,right,up,down,early) < score(xStop,yStop,left,right,up,down,late)){
                maxTime = late;
            }
            else minTime = early;
        }
        System.out.println(score(xStop,yStop,left,right,up,down,minTime));

    }
}