题目描述

在20015年，JAG（Jagan加速组）成功发明了一种名为“Force Point”的新型加速器，用于对二维$xy$平面上的质子碰撞进行实验。如果一个质子碰触到Force Point，它的速度将加倍，并且其运动方向将被改变。质子可能通过四种方式受到Force Field的影响：平行于$x$轴或$y$轴的正向或负向方向。质子偏离的方向取决于Force Point的类型。Force Point只能加速质子一次，因为加速后立即消失。在二维平面上生成许多Force Point，称为2D Force Point Field，通过连续使用Force Points加速质子，可以将其加速到目标速度。

Force Point的生成方法仍在实验中，JAG具有以下技术限制：

• JAG不能生成具有指定位置和类型的Force Point。
• JAG不能在将质子放入2D Force Point Field之后生成Force Point。
• JAG不能移动Force Points。
• JAG不能改变质子的方向，除非受到Force Points的影响。
• JAG只能将一个质子用于2D Force Point Field。
• JAG可以将以任意方向和速度1运动的质子放置在2D Force Point Field的任何位置。

为了使质子达到最大速度，JAG的工程师必须选择质子的最佳初始位置和最佳初始方向，以便质子在仔细观察生成的2D Force Point Field后尽可能多地受到Force Points的加速。

通过观察生成的2D Force Point Field，已知生成的Force Points的数量为$n$。已知第$i$个点的位置（$x\_i$，$y\_i$）和偏转类型$d\_i$。您的任务是编写一个程序，在JAG进行最佳放置时，计算给定2D Force Point Field上质子的最大速度。

输入

输入包含一个单独的测试用例，描述了以下格式的2D Force Point Field。

$n$ $x\_1$ $y\_1$ $d\_1$ ... $x\_n$ $y\_n$ $d\_n$

第一行包含一个整数$n$($1\le n\le 3,000$)，表示2D Force Point Field上的Force Points的数量。接下来的$n$行中的每一行包含两个整数$x\_i$和$y\_i$($|x\_i|, |y\_i| \le 10^9$)以及一个字符$d\_i$($d\_i$是'>'，'v'，'<'或'^'中的一个)。$x\_i$和$y\_i$表示第$i$个Force Point的坐标，$d\_i$是第$i$个force point的方向偏移类型。类型'>'的force point将质子的方向改变为$x$轴的正方向，'v'表示$y$轴的正方向，'<'表示$x$轴的负方向，'^'表示$y$轴的负方向。您可以假设任意两个Force Points不会在相同的坐标上生成。

输出

显示一行，其中包含整数$\\log\_2 v\_{\\mathrm{max}}$，其中$v\_{\\mathrm{max}}$是质子可能的最快速度。

示例输入1

9
0 0 v
1 0 >
2 0 <
0 1 >
1 1 v
2 1 v
0 2 ^
1 2 ^
2 2 <```

### 示例输出1

```plain
9```

输入看起来像下面的示意图。如果将质子放在$(1, 1)$处，所有的Force Points都会消失。

```plain
v><
>vv
^^<```

### 示例输入2

```plain
9
0 0 ^
1 0 ^
2 0 ^
0 1 <
1 1 ^
2 1 >
0 2 v
1 2 v
2 2 v```

### 示例输出2

```plain
2```