You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Alice 想要拍一张夜空的照片，她把夜空抽象为平面直角坐标系，有 $n$ 颗星星，第 $i$ 颗星星的坐标为 $(x_i,y_i)$ ，颜色为 $c_i$ （有红，蓝，绿三种颜色，分别用大写字母R，B，G来表示。

照片是一个矩形，四条边分别平行于平面直角坐标系的两个轴，如果第 $i$ 颗星星的坐标满足 $x_l \le x_i \le x_r,y_l \le y_i \le y_r$ ，那么就说这颗星星被拍到了照片里，这张照片长为 $x_r-x_l+1$ ，宽为 $y_r-y_l+1$ ，照片占用内存为 $(x_r-x_l+1)(y_r-y_l+1)$ 。

Alice想要让照片中包含三种颜色的星星，她想知道照片最小占用内存是多少。

输入格式

第一行一个整数 $n$ 表示星星的数量。

接下来 $n$ 行，每行两个整数，一个字符，分别为 $x_i,y_i,c_i$ 。

注意：不同星星的坐标可能相同。

输出格式

一行一个整数，表示照片最小占用内存，如果无论如何都拍不出包含三种颜色的照片，请输出 $-1$ 。

输入输出样例 #1

输入 #1

6
1 2 B
1 1 R
2 1 G
2 0 G
0 -1 B
3 1 R

输出 #1

4

输入输出样例 #2

输入 #2

2
0 0 R
0 0 B

输出 #2

-1

输入输出样例 #3

输入 #3

3
0 0 R
0 0 B
0 0 G

输出 #3

1

说明/提示

对于 $20\%$ 数据，$x_i=y_i=0$ 。

对于另外 $30\%$ 数据， $-10 \le x_i,y_i \le 10$ 。

对于另外 $30\%$ 数据， $-10^4 \le x_i,y_i \le 10^4$ 。

对于全部数据 $1 \le n \le 100,-10^8 \le x_i,y_i \le 10^8,c_i \in \{'R','B','G'\}$ 。