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>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
template<class T> bool umin(T &x,T y) { if (x<y) return 0; x=y; return 1; }
template<class T> bool umax(T &x,T y) { if (x>y) return 0; x=y; return 1; }
using ll = long long;
using ld = long double;

int const INF=1e9;

struct dist_func {
	ll l1,r1,l2,r2,m1,m2;
	vector<ll> ts;
	
	dist_func(ll a,ll b,ll c,ll d,ll e,ll f): l1(a),r1(b),l2(c),r2(d),m1(e),m2(f) {
		ts.push_back(0);
		while (true) {
			ll nt=find_next(ts.back());
			if (nt==INF) break;
			ts.push_back(nt);
		}
	}
	
	ll eval(ll t) const {
		return max({r1+t,r2-t,m2})-min({l1+t,l2-t,m1});
	}
	
	ll operator()(ll t) const {
		return eval(t);
	}
	
	ll find_next(ll t) {
		ll s=eval(t+1)-eval(t);
		ll l=t,r=INF;
		while (l<r) {
			ll m=l+(r-l)/2;
			if (eval(m+1)-eval(m)==s) l=m+1; else r=m;
		}
		return l;
	}
};

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	ll r1,r2,l1,l2,x1,x2,d1,d2,u1,u2,y1,y2;
	r1=l1=x1=d1=u1=y1=INF;
	r2=l2=x2=d2=u2=y2=-INF;
	
	int N;
	cin>>N;
	rep(i,0,N) {
		ll x,y;
		string s;
		cin>>x>>y>>s;
		x*=2;
		y*=2;
		switch (s[0]) {
			case 'R':
				umin(r1,x),umax(r2,x),umin(y1,y),umax(y2,y);
				break;
			case 'L':
				umin(l1,x),umax(l2,x),umin(y1,y),umax(y2,y);
				break;
			case 'U':
				umin(u1,y),umax(u2,y),umin(x1,x),umax(x2,x);
				break;
			case 'D':
				umin(d1,y),umax(d2,y),umin(x1,x),umax(x2,x);
				break;
			default:
				throw;
		}
	}

	dist_func dx(r1,r2,l1,l2,x1,x2);
	dist_func dy(u1,u2,d1,d2,y1,y2);

	ll res=dx(0)*dy(0);
	for (ll t:dx.ts) umin(res,dx(t)*dy(t));
	for (ll t:dy.ts) umin(res,dx(t)*dy(t));
	cout<<ld(res)/4<<"\n";	
}