2048 is a well-known game, if you hasn't play it before, play it now!
How to play 2048:
You can choose to move all the tiles to 4 directions: up, down, left, right. Tiles with the same number merge into one when they touch and the value becomes their sum. After that, the board will radomly gernerate new tile on the tile that is empty. Game ends when you get the tile with value 2048 or their's no way to move. For more information, please refer to link.
Now you're asked to write a program to move/merge the tiles with the given board and direction to move. You don't have to implement the part that generates new tiles randomly.
Input contains multiple testcases, you have to read the input until EOF.
Each testcase contains a 4 by 4 grid representing the board of the game. The number on it is less than 2048 and it should be a power of 2 except 1 and 0 represents empty.
Output the board after moving up/down/left/right respectively.
If nothing happen when moving on that direction, output "Invalid".