题目描述

$2048$ 是一款著名的单人游戏，目标是在网格上滑动方块使它们合并，并创建一个写有数字 $2048$ 的方块。

$2048$ 在一个简单的 $4 \times 4$ 网格上进行，当玩家移动方块时，方块会平滑地滑动。每次移动时，玩家可以选择同时将所有方块向 $4$ 个方向——左、右、上、下——尽可能远地移动。如果两个数值相同的方块在移动中相撞，它们会合并成一个方块，其数值为相撞的两个方块的数值之和。在一次移动中，新生成的方块不能再次合并，并且总是优先与沿移动方向相邻的方块合并。 例如，如果三个 "2" 排成一行 "2 2 2" 并且玩家选择向左移动，结果会变成 "4 2 0"，最左边的两个 "2" 会合并。

:::align{center} :::

上图展示了当玩家将所有方块向右移动时，$4 \times 4$ 网格的变化情况。

Alice 和 Bob 偶然发现了这个游戏，并爱上了两个方块合并时的感觉。玩了几轮后，他们开始对棋盘的大小感到厌倦，于是决定将棋盘尺寸扩展到 $\mathbf{N} \times \mathbf{N}$，并将该游戏称为“Super 2048”。

大棋盘随后让他们眼花缭乱（不作死就不会死 -_-| ）。他们请你编写一个程序，帮助他们计算在给定棋盘上将所有方块向某一特定方向移动后，棋盘会变成什么样子。

输入格式

输入的第一行给出测试用例的数量 $\mathbf{T}$。接下来是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行给出棋盘的边长 $\mathbf{N}$ 以及方块将要移动的方向 DIR。$\mathbf{N}$ 和 DIR 由一个空格分隔。DIR 将是四个字符串之一："left"（左）、"right"（右）、"up"（上）或 "down"（下）。

接下来的 $\mathbf{N}$ 行每行包含 $\mathbf{N}$ 个以空格分隔的整数，描述棋盘的初始状态。每一行代表棋盘的一行（从上到下）；每个整数代表方块上的数值（若该位置没有方块则为 $0$）。

输出格式

对于每个测试用例，首先输出一行 "Case #x:"，其中 $x$ 是测试用例编号（从 $1$ 开始）。然后再输出 $\mathbf{N}$ 行，每行包含 $\mathbf{N}$ 个以空格分隔的整数，按照与输入相同的格式描述移动后的棋盘。

3
4 right
2 0 2 4
2 0 4 2
2 2 4 8
2 2 4 4
10 up
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 right
2 2 2
4 4 4
8 8 8

Case #1:
0 0 4 4
0 2 4 2
0 4 4 8
0 0 4 8
Case #2:
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Case #3:
0 2 4
0 4 8
0 8 16

提示

限制

网格中的每个数字要么为 $0$，要么是 $2$ 到 $1024$（含两端）之间的 $2$ 的幂。

小数据集（测试集 1 - 可见）

$1 \le T \le 20$

$1 \le \mathbf{N} \le 4$

大数据集（测试集 2 - 隐藏）

$1 \le T \le 100$

$1 \le \mathbf{N} \le 20$

翻译由 DeepSeek V4 Pro 完成