벡터 필드

20015년, JAG(Jagan Acceleration Group)는 2차원 $xy$ 평면에서 양성자 충돌 실험에 쓸 새 가속기 "Force Point"를 개발했다. 양성자가 Force Point에 닿으면 속력이 두 배가 되고 진행 방향이 바뀐다. 새 방향은 x축 또는 y축과 평행한 양의 방향이나 음의 방향, 네 가지 중 하나다. 방향은 Force Point의 종류가 정한다. Force Point는 양성자를 한 번만 가속하고 바로 사라진다. 평면에 놓인 Force Point의 집합을 2D Force Point Field라고 부른다. Force Point를 차례로 통과시키면 양성자를 목표 속력까지 가속할 수 있다.

JAG에는 다음 기술적 한계가 있다.

• JAG는 위치와 종류를 지정해서 Force Point를 만들 수 없다.
• JAG는 양성자를 필드에 넣은 뒤에는 Force Point를 만들 수 없다.
• JAG는 Force Point를 옮길 수 없다.
• JAG는 Force Point의 작용 말고는 양성자의 방향을 바꿀 수 없다.
• JAG는 2D Force Point Field 하나에 양성자 한 개만 사용할 수 있다.
• JAG는 임의의 방향으로 속력 1로 움직이는 양성자를 필드의 임의의 위치에 놓을 수 있다.

최대 속력을 얻으려면 엔지니어가 생성된 필드를 관찰한 뒤, 양성자가 가능한 한 많은 Force Point의 가속을 받도록 초기 위치와 초기 방향을 최적으로 골라야 한다.

필드의 Force Point 개수는 $n$이고, 각 점의 위치 $(x_i, y_i)$와 방향 종류 $d_i$가 주어진다. JAG가 양성자를 최적으로 놓았을 때 얻을 수 있는 최대 속력을 계산하는 프로그램을 작성하라.

입력은 다음 형식의 테스트 케이스 하나이다.

$n$

$x_1$ $y_1$ $d_1$

...

$x_n$ $y_n$ $d_n$

첫 줄에는 Force Point의 개수를 나타내는 정수 $n$ ($1\le n\le 3{,}000$)이 있다. 다음 $n$개 줄에는 정수 $x_i$, $y_i$ ($|x_i|, |y_i| \le 10^9$)와 문자 $d_i$가 있다. $d_i$는 '>', 'v', '<', '^' 중 하나다. '>'는 양의 x축 방향, 'v'는 양의 y축 방향, '<'는 음의 x축 방향, '^'는 음의 y축 방향으로 양성자의 방향을 바꾼다. 같은 좌표에 두 Force Point가 생성되는 경우는 없다.

$v_{\mathrm{max}}$를 양성자가 도달할 수 있는 가장 빠른 속력이라 할 때, $\log_2 v_{\mathrm{max}}$의 값을 정수로 한 줄에 출력한다.