그리드락

Foolish Puzzle Company는 새 퍼즐을 소개하는 광고를 올렸다. 광고에는 매우 비효율적인 플레이 방식이 나온다. "99.99% cant solve these puzle"이라는 문구에 자극을 받아 이 퍼즐을 내려받았다. 한참 시간을 허비한 뒤에야 레벨이 점점 커지고 재미가 사라졌다는 것을 알게 되었다. 그래서 레벨을 자동으로 풀고, 불가능한 레벨은 건너뛰는 프로그램을 짜기로 했다.

레벨은 블록이 채워진 직사각형 격자다. 각 블록에는 위, 아래, 왼쪽, 오른쪽 중 한 방향을 가리키는 화살표가 있다. 블록은 화살표가 가리키는 방향으로 밀어서 꺼낸다. 블록은 격자 밖으로 완전히 나갈 때까지 밀어야 한다. 중간까지만 밀고 다른 블록을 민 뒤 같은 블록을 다시 밀어 꺼내는 것은 허용되지 않는다.

모든 블록을 꺼낼 수 있는 순서를 찾거나, 모든 블록을 꺼내는 것이 불가능하다고 답하라.

첫 줄에 격자의 행 수와 열 수를 나타내는 두 정수 $h$와 $w$ ($1\leq h, w\leq 2000$)가 주어진다.

이어지는 $h$개의 줄에는 각각 길이가 $w$인 문자열이 주어진다. 문자열은 "<", "^", ">", "v"로 이루어지며, 각 문자는 그 블록이 가리키는 방향이다.

격자를 풀 수 있으면 블록을 꺼낸 순서대로 $h \cdot w$쌍의 수 $y$와 $x$ ($1 \leq y,x \leq n$)를 출력한다. 각 쌍은 꺼낸 블록의 행과 열이다.

격자를 풀 수 없으면 "impossible"을 출력한다.

풀이가 여러 개라면 그중 아무거나 출력해도 된다.