Problem B
BBBBBB

Our favourite game developer Saskia has started on a new game, called BBBBBB! In this game, you’re Captain Biryan and have to save your crew. They have been scattered around in an alternate dimension named bbbbbb.

The game consists of a number of puzzles in a 2D grid, where you are the @ symbol and have to get to the X. # represents immovable blocks, and ^ and v are deadly spikes. The player, playing Captain Biryan, can do one of three actions:

• Move one tile right (if the tile does not contain a #)

• Move one tile left (if the tile does not contain a #)

• Flip gravity: If gravity is pulling down, it is now pulling you up instead (and vice versa)

Figure 1: Sample Input 1, and one of the ways to the X with the least number of gravity flips.

The game logic is rather short and can be summarised by this pseudocode:

gravity_direction = down
while true:
  if player is at the location of the 'X':
    return WIN
  if player is at the location of a '^' or 'v':
    return DEAD
  if player does not touch the ground:
    player_y += 1 * gravity_direction
    continue (restart loop from the top)
  if player touches the ground:
    perform_next_player_action()

Touching the ground is defined as being placed exactly one tile above or below a #, depending on which way gravity pulls.

To ensure that there’s a good variety of puzzles in the game, Saskia wants to implement a shortest path algorithm that finds the minimum number of gravity flips needed to solve a puzzle.

Input

The first line consists of two integers $W$ and $H$, representing the width and the height of the 2D grid to be parsed.
Then follows $H$ lines each consisting of a string of length $W$. Each string can only contain the characters ‘ ’, ‘#’, ‘v’, ‘^’, ‘@’ and ‘X’.

Output

Output the minimum number of gravity flips needed to solve the puzzle, along with the number of user actions needed. If there are multiple solutions with the same number of gravity flips, output the one with the least amount of user actions needed.
If there is no valid path to the exit, output ‘impossible!’ (without the quotes).

Limits

• $4 \leq W, H \leq 450$

• The border of the map can only contain ‘#’, ‘v’ and ‘^’ tiles.

• The grid will only contain the characters‘ ’, ‘#’, ‘v’, ‘^’, @ and X, and there will be exactly one @ and one X symbol in the grid.

11 6
#####vv####
#     #   #
#         #
# #####v  #
#   @    X#
######^^###

4 15

10 4
#^^^^^^^^#
#        #
#@      X#
##vvvvvv##

impossible!