You found a weird puzzle in a box with old toys in your attic. The puzzle forms a rectangular grid board made of h×w square cells. Some cells in that grid have a colored tile placed on them, as shown in Figure 1.

Figure 1: Color tiles correspond to the starting arrangement in Sample Input 1.

You are not yet sure what the exact goal of this puzzle is, but you started examining possible ways of rearranging the tiles. Their arrangement can be manipulated by tilting the grid in one of the four cardinal directions: to your left, to your right, towards you, or away from you. Tilting causes all the tiles to slide in the respective direction until they are blocked either by the boundary or by another tile. Given a starting and ending arrangement, determine whether there exists some sequence of tilts that transforms the former into the latter. Figure 2 illustrates tilting of the puzzle shown in Sample Input 1.

Figure 2: Solution to Sample Input 1.

#8289 upload - done - how_to_reg -

Tilting Tiles timer 3s memory 1024MB

#8289

Tilting Tiles 3s 1024MB