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

Solution:
#include<bits/stdc++.h>
using namespace std;
#define double long double

vector<double> x[3],y[3]; 
int n;
double mi3(double _a,double _b,double _c){
	return min(_a, min(_b,_c));
}
double ma3(double _a,double _b,double _c){
	return max(_a, max(_b,_c));
}
double area(double t){
	double low_x = 100000000000.0;
	double low_y = 100000000000.0;
	double high_x = - 100000000000.0;
	double high_y = - 100000000000.0;
	if(x[0].size()) {
		low_x = min(low_x, x[0][0]);
		high_x = max(high_x, x[0][x[0].size() - 1]);
	}
	if(y[0].size()) {
		low_y = min(low_y, y[0][0]);
		high_y = max(high_y, y[0][y[0].size() - 1]);
	}
	if(x[1].size()) {
		low_x = min(low_x, x[1][0] - t);
		high_x = max(high_x, x[1][x[1].size() - 1] - t);
	}
	if(y[1].size()) {
		low_y = min(low_y, y[1][0] - t);
		high_y = max(high_y, y[1][y[1].size() - 1] - t);
	}
	if(x[2].size()) {
		low_x = min(low_x, x[2][0] + t);
		high_x = max(high_x, x[2][x[2].size() - 1] + t);
	}
	if(y[2].size()) {
		low_y = min(low_y, y[2][0] + t);
		high_y = max(high_y, y[2][y[2].size() - 1] + t);
	}
	return (high_x - low_x) * (high_y - low_y);
}
double search(double l,double r){
	double it = 1000000;
	while(it --){
		double m1 = l + (r - l) / 3.0;
		double m2 = r - (r - l) / 3.0;
		if(area(m1) < area(m2)) r = m2;
		else l = m1;
	}
	return area(l);
}
signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		double _x, _y;
		char c;
		cin >> _x >> _y >> c;
		if(c == 'L' || c == 'R'){
			y[0].push_back(_y);
			x[(c == 'L' ? 1: 2)].push_back(_x);
		} else{
			x[0].push_back(_x);
			y[(c == 'D' ? 1: 2)].push_back(_y);
		}
	}
	for(int i = 0 ; i <= 2 ; i ++){
		sort(x[i].begin(),x[i].end());
		sort(y[i].begin(),y[i].end());
	}
	
	cout << setprecision(10) << search(0, 1000000000.0);
	
}