2048

In the game 2048, you are given a 4 by 4 board of numbers (some of them empty, represented in our case with 0) which you can swipe in any of the 4 directions ("up", "down", "left", or "right"). When you swipe, all the numbers move in that direction as far as possible and identical adjacent numbers are combined to form their sum exactly once. Given a 2D matrix of integers board representing the initial board and a string direction representing the swipe direction, implement the next board state.

Constraints

• n = 4 where n is the number of rows and columns in board

https://binarysearch.com/problems/2048

Examples

Example 1

Input

• board =

[[2,0,0,2],
 [2,2,2,2],
 [0,4,2,2],
 [2,2,2,0]]

• direction = left

Output

• answer = [[4, 0, 0, 0], [4, 4, 0, 0], [4, 4, 0, 0], [4, 2, 0, 0]]

Explanation

All the values are moved as leftmost as possible and identical adjacent values are merged exactly once, starting from the end.

Solution