Gridlock

The Foolish Puzzle Company posted an advertisement for a new puzzle that shows a very inefficient way of playing. Taunted by the "99.99% cant solve these puzle" caption, you downloaded the puzzle. After wasting a good amount of time, you noticed the levels keep getting larger and the game is no longer fun. So you decide to write a program that solves the levels automatically and skips the impossible ones.

A level is a rectangular grid of blocks. Each block has an arrow pointing up, down, left, or right. You remove a block by sliding it in the direction of its arrow. A block must slide all the way out of the grid. You cannot slide it partway, slide another block, and then slide the first block out later.

Find an order that removes all the blocks, or state that it is impossible to remove all of them.

The first line contains two integers $h$ and $w$ ($1\leq h, w\leq 2000$), the number of rows and columns of the grid.

The next $h$ lines each contain a string of length $w$ made of the characters "<", "^", ">", and "v". Each character gives the direction of the block.

If the grid can be solved, print $h \cdot w$ pairs of numbers $y$ and $x$ ($1 \leq y,x \leq n$), one pair per block, in the order the blocks are removed. Each pair is the row and column of the block.

If it is impossible to solve the grid, print "impossible".

If there are multiple valid solutions, you may print any of them.