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.

题目描述

有一个点集 $S$，要满足下面三类限制：

• P x y，要求 $(x,y)\in S$。
• H x y，要求对任意 $y_0$，$(x,y_0)\in S$ 当且仅当 $(x,y-y_0)\in S$。
• V x y，要求对任意 $x_0$，$(x_0,y)\in S$ 当且仅当 $(x-x_0,y)\in S$。

求符合要求的 $S$ 元素数最小值。

输入格式

输入的第一行是 $n$ 表示操作个数。

之后 $n$ 行每行首先是一个字符，然后输入两个整数，表示一个限制。

输出格式

输出一行一个整数，如果存在有限集 $S$ 符合题意则输出该集合元素数，否则输出 $-1$。

样例

样例输入 1

8
H -1 3
P 2 2
V 0 1
V 2 2
P 1 1
V 0 1
V 800 800
V 802 800

样例输出 1

6

样例输入 2

4
P 1 2
H 1 6
V 0 4
V 3 4

样例输出 2

-1

提示

【样例 1 解释】

由 P 1 1 和 V 0 1，也就是 $(1,1)\in S$ 和 $(x,1)\in S\iff (0-x,1)\in S$ 可知 $(-1,1)\in S$。

接下来将 $(-1,1)\in S$ 代入 H -1 3 可得 $(-1,2)\in S$。

分别将 $(-1,2),(2,2)\in S$ 代入 V 2 2 可得 $(3,2),(0,2)\in S$。

最终 $S$ 至少要有 $(1,1),(-1,1),(-1,2),(0,2),(2,2),(3,2)$ 六个点。

【样例 2 解释】

将 $(1,2)$ 代入 H 1 6，得 $(1,4)\in S$。

接下来将 $(x,4)$ 代入 V 0 4，可得 $(-x,4)\in S$。

然后将 $(-x,4)$ 代入 V 3 4，可得 $(x+3,4)\in S$。

因此 $(1,4),(4,4),(7,4),\ldots$ 都在 $S$ 内，$S$ 是无限集。

【数据范围】

$m$ 表示 H 类限制和 V 类限制数总和。

上述表格中，留空表示该栏和全部数据的限制相同。

对于全部数据，输入皆为整数，$0\le n,m\le 10^6$，$x,y\in[-10^3,10^3]$。