Vector Field

In 20015, JAG (Jagan Acceleration Group) built a new accelerator called "Force Point" for proton collision experiments on the two-dimensional $xy$-plane. When a proton touches a Force Point, its speed doubles and its direction changes. The new direction is one of four: the positive or negative direction of the $x$-axis or the $y$-axis. The type of the Force Point determines the direction. A Force Point accelerates a proton only once, then it disappears. A set of Force Points on the plane is called a 2D Force Point Field. Passing a proton through the Force Points in sequence can accelerate it up to a target speed.

JAG has these technical limitations:

• JAG cannot generate a Force Point at a specified position with a specified type.
• JAG cannot generate a Force Point after a proton is put into the field.
• JAG cannot move Force Points.
• JAG cannot change a proton's direction except through Force Points.
• JAG can use only one proton for each 2D Force Point Field.
• JAG can place a proton moving in any direction with speed 1 at any position in the field.

To reach the maximum speed, the engineers must observe the generated field, then pick the initial position and initial direction of the proton so that it is accelerated by as many Force Points as possible.

The field has $n$ Force Points. The position $(x_i, y_i)$ and the direction type $d_i$ of each point are known. Write a program that computes the maximum speed a proton can reach when JAG places the proton optimally.

The input is a single test case in this format:

$n$

$x_1$ $y_1$ $d_1$

...

$x_n$ $y_n$ $d_n$

The first line contains one integer $n$ ($1\le n\le 3{,}000$). Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 10^9$) and one character $d_i$, which is one of '>', 'v', '<', or '^'. The type '>' sends the proton in the positive $x$ direction, 'v' in the positive $y$ direction, '<' in the negative $x$ direction, and '^' in the negative $y$ direction. No two Force Points share the same coordinates.

Print one line with the integer $\log_2 v_{\mathrm{max}}$, where $v_{\mathrm{max}}$ is the fastest speed the proton can reach.