P16478 [GKS 2014 #A] Super 2048

$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}$ 个以空格分隔的整数，按照与输入相同的格式描述移动后的棋盘。

### 限制 网格中的每个数字要么为 $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 完成