#include<set>
#include<ctime>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+7;
int read(){
	char c;
	int x=0,f=1;
	while(!isdigit(c=getchar()))
		f-=2*(c=='-');
	while(isdigit(c)){
		x=x*10+f*(c-48);
		c=getchar();
	}
	return x;
}
struct que{
	int p,i,r;
	que(int a=0,int b=0,int c=0){
		p=a;
		i=b;
		r=c;
	}
	friend bool operator <(que a,que b){
		return a.p<b.p;
	}
};
struct sol{
	int a,b,c,d;
	sol(int A=0,int B=0,int C=0,int D=0){
		a=A;
		b=B;
		c=C;
		d=D;
	}
};
int c[N];
bool vis[N];
int n,x,y,r,k,tot;
vector<que>l[N];
sol ans[N];
int abs(int x){
	return x>0?x:-x;
}
int random(int l,int r){
	return rand()%(r-l+1)+l;
}
int calc(int a,int b,int c,int d,int r){
	return abs((b-a)*(d-c)-r);
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("0014.txt","r",stdin);
	freopen("A.out","w",stdout);
	#endif
	clock_t t1=clock();
	//--------
	n=read();
	srand(210280344);
	for(int i=1;i<=n;++i){
		x=read();
		y=read();
		r=read();
		l[x].push_back(que(y,i,r));
		vis[x]=1;
	}
	for(int i=0;i<N-7;++i){
		if(vis[i]){
			++tot;
			c[tot]=i;
			sort(l[i].begin(),l[i].end());
		}
	}
	c[tot+1]=N-7;
	for(int i=1;i<=tot;++i){
		int A;
		int B;
		int C;
		int D;
		int sz=l[c[i]].size();
		if(i==1)
			A=random(0,c[i]);
		else
			A=random(c[i-1],c[i]);
		C=random(c[i]+1,c[i+1]);
		B=random(0,l[c[i]][0].p);
		if(sz==1){
			k=1e9;
			r=l[c[i]][0].r;
			for(int ii=1;ii<N;++ii){
				int t=random(l[c[i]][0].p+1,N-7);
				int s=calc(A,B,C,t,r);
				if(k>s){
					k=s;
					D=t;
				}
			}
			ans[l[c[i]][0].i]=sol(A,B,C,D);
			c[i]=C;
			continue;
		}
		k=1e9;
		r=l[c[i]][0].r;
		for(int ii=1;ii<N;++ii){
			int t=random(l[c[i]][0].p+1,l[c[i]][1].p);
			int s=calc(A,B,C,t,r);
			if(k>s){
				k=s;
				D=t;
			}
		}
		l[c[i]][0].p=D;
		ans[l[c[i]][0].i]=sol(A,B,C,D);
		for(int j=1;j<sz-1;++j){
			B=random(l[c[i]][j-1].p,l[c[i]][j].p);
			k=1e9;
			r=l[c[i]][j].r;
			for(int ii=1;ii<N;++ii){
				int t=random(l[c[i]][j].p+1,l[c[i]][j+1].p);
				int s=calc(A,B,C,t,r);
				if(k>s){
					k=s;
					D=t;
				}
			}
			l[c[i]][j].p=D;
			ans[l[c[i]][j].i]=sol(A,B,C,D);
		}
		B=random(l[c[i]][sz-2].p,l[c[i]][sz-1].p);
		k=1e9;
		r=l[c[i]][sz-1].r;
		for(int j=1;j<=N-7;++j){
			int t=random(l[c[i]][sz-1].p+1,N-7);
			int s=calc(A,B,C,t,r);
			if(k>s){
				k=s;
				D=t;
			}
		}
		ans[l[c[i]][sz-1].i]=sol(A,B,C,D);
		c[i]=C;
	}
	for(int i=1;i<=n;++i){
		int A=ans[i].a;
		int B=ans[i].b;
		int C=ans[i].c;
		int D=ans[i].d;
		printf("%d %d %d %d\n",A,B,C,D);
	}
	//--------
	fprintf(stderr,"%0.3lfs",1.0*(clock()-t1)/CLOCKS_PER_SEC);
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    
    ll n; cin >> n;
    ll a[2 * n]; char c[2 * n]; zep(i, 0, 2 * n)cin >> a[i] >> c[i];

    multiset<ll> s[3];
    zep(i, 0, 2 * n){
        s[c[i] % 3].insert(a[i]);
    }

    if(s[0].size() % 2 == 0 && s[1].size() % 2 == 0 && s[2].size() % 2 == 0){
        print(0) return 0;
    }
    // cout << 'R' % 3 << 'G' % 3 << 'B' % 3 << endl;
    ll v[3][3];
    zep(i, 0, 3)zep(j, 0, 3)v[i][j] = INF;
    zep(i, 0, 3){
        zep(j, 0, 3){
            for(auto it = s[i].begin(); it != s[i].end(); it++){
                ll x = *it;
                if(s[j].lower_bound(x) != s[j].end()){
                    ll y = *s[j].lower_bound(x);
                    v[i][j] = min(v[i][j], y - x);
                    v[j][i] = min(v[j][i], y - x);
                }
            }
        }
    }
    //zep(i, 0, 3){zep(j, 0, 3)cout << v[i][j] << " "; cout << endl;}

    zep(i, 0, 3){
        if(s[i].size() % 2 == 0){
            print(min(v[(i + 1) % 3][(i + 2) % 3], v[i][(i + 1) % 3] + v[i][(i + 2) % 3]))
            return 0;
        }
    }

    return 0;
}