На интернету је веома популарна игра 2048. На квадратој табли неке плочице садрже степене броја 2, а нека поља су празна. Играч игра потез тако што се одлучи за један смер (налево, надесно, наниже или навише) и затим помера све плочице преко празних поља у том смеру, колико год је то могуће. При том се две плочице на којима пише исти број, а које су које су суседне (или које постају суседне након померања плочица по празним пољима) спајају у једну плочицу на којој је дупло већи број (спајање се врши у правцу кретања). Плочице настале спајањем се не спајају даље током истог потеза. Слободно играјте мало игрицу да бисте схватили правила.

Улаз

Са стандардног улаза се уноси број \(n\) (\(1 \leq n \leq 10\)), а затим и матрица димензије \(n\times n\) на којој су празна поља означена вредношћу 0, а плочице степенима двојке. У наредном реду се налази један карактер који одређује смер померања (L - налево, D - надесно, V - навише, N - наниже).

Излаз

На стандардни излаз исписати матрицу која представља стање табле за игру након одиграног потеза.

Пример 1

Улаз

4
1 2 4 8
2 2 4 0
2 2 0 4
0 1 2 4
L

Излаз

1 2 4 8
4 4 0 0
4 4 0 0
1 2 4 0

Пример 2

Улаз

4
0 0 0 2
0 0 2 0
0 2 0 0
2 0 0 0
N

Излаз

0 0 0 0
0 0 0 0
0 0 0 0
2 2 2 2

Пример 3

Улаз

4
0 0 2 2
0 2 0 2
2 0 0 2
2 2 2 2
D

Излаз

0 0 0 4
0 0 0 4
0 0 0 4
0 0 4 4

Пример 4

Улаз

4
0 0 0 2
0 0 2 2
0 2 2 2
2 2 2 2
V

Излаз

2 4 4 4
0 0 2 4
0 0 0 0
0 0 0 0