2015 年，JAG（Jagan Acceleration Group）成功发明了一种名为“力点”（Force Point）的新型加速器，用于二维 $xy$ 平面上的质子碰撞实验。如果质子接触到一个力点，它的速度会加倍，且运动方向会发生改变。质子在力场的作用下可以有四种转向方式：平行于 $x$ 轴或 $y$ 轴的正方向或负方向。质子转向的方向由力点的类型决定。每个力点只能加速质子一次，因为力点在加速后会立即消失。在二维平面上生成许多力点（称为二维力点场），可以通过依次利用这些力点加速质子，使其达到目标速度。

力点的生成方法尚处于实验阶段，JAG 面临以下技术限制：

• JAG 无法生成具有指定位置和类型的力点。
• JAG 无法在将质子放入二维力点场后生成力点。
• JAG 无法移动力点。
• 除力点的影响外，JAG 无法改变质子的运动方向。
• JAG 在一个二维力点场中只能使用一个质子。
• JAG 可以将一个以速度 1 运动的质子以任意方向放入二维力点场的任意位置。

为了使质子的速度达到最大，JAG 的工程师必须在仔细观察生成的二维力点场后，选择质子的最佳初始位置和最佳初始方向，以便质子能尽可能多地被力点加速。

通过观察生成的二维力点场，已知生成的力点数量为 $n$。第 $i$ 个力点的位置 $(x_i, y_i)$ 和转向类型 $d_i$ 也是已知的。你的任务是编写一个程序，计算当 JAG 最优地放置质子时，质子在给定的二维力点场中加速后能达到的最大速度。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3000$)，表示二维力点场中力点的数量。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($|x_i|, |y_i| \le 10^9$) 以及一个字符 $d_i$ ($d_i$ 为 ‘>’, ‘v’, ‘<’ 或 ‘^’ 之一)。$x_i$ 和 $y_i$ 表示第 $i$ 个力点的坐标，$d_i$ 是第 $i$ 个力点的转向类型。类型为 ‘>’ 的力点将质子的方向改变为 $x$ 轴正方向，‘v’ 表示 $y$ 轴正方向，‘<’ 表示 $x$ 轴负方向，‘^’ 表示 $y$ 轴负方向。你可以假设任意两个力点不会生成在相同的坐标上。

输出格式

输出一行，包含整数 $\log_2 v_{max}$，其中 $v_{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

9

输入 2

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

输出 2

2

说明

第一个样例输入看起来像下面的图示：

v><
>vv
^^<

如果你将质子放在 $(1,1)$，所有的力点都会消失。