时空限制

1S/512M

题目描述

在一个物流仓库中，机械臂突然发生故障，导致所有悬挂在空中的货物箱子同时垂直掉落。

仓库场景可以用一个 $n \times m$ 的网格表示，每个格子包含以下三种字符之一：

• . 表示空地。
• - 表示坚硬平台（固定障碍物，悬浮在空中或地面，不可穿过）。
• 大写字母表示货物箱子。

所有箱子同时垂直下落，直到遇到以下情况之一才会停止：

1. 网格的底部
2. 坚硬平台 -
3. 其他箱子（包括摔碎后变成的废墟）

每个箱子从初始位置 $(r_{start}, c)$ 下落到静止位置 $(r_{end}, c)$，定义其下落距离 $d = r_{end} - r_{start}$。

每个箱子都有一个耐摔程度 $k$：

• 若 $d \le k$：箱子完好，保持原字母
• 若 $d > k$：箱子摔碎，变为废墟字符 *。

注意：废墟 * 仍然占据该格子，可以支撑落在上方的物体。

请你输出所有箱子下落后的最终网格。

格式

输入格式

第一行包含三个整数 $n, m, k$，分别表示网格的行数、列数和箱子的耐摔程度。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示掉落前的初始状态。字符集为 .、- 和 A-Z。

输出格式

输出 $n$ 行，每行 $m$ 个字符，表示掉落并结算后的最终状态。

样例

样例输入 #1

4 2 1
A.
..
.B
-.

样例输出 #1

..
..
*.
-B

样例解释 #1

对于箱子 A： 箱子 A 原本在第 1 行，掉落到第 3 行（停在 - 上方）。此时下落距离 $d = 3 - 1 = 2$。因为 $2 > k$，A 被摔碎，最终在第 $3$ 行显示为 *。

对于箱子 B：箱子 B 原本在第 3 行。下方无障碍，直接掉落至第 4 行（网格底部）。此时下落距离 $d = 4 - 3 = 1$。因为 $1 \le k$，B 完好，最终在第 $4$ 行显示为 B。

数据规模

对于 $30\%$ 的数据， $1 \leq n, m \le 100$。

对于 $100\%$ 的数据，$1 \le n, m \le 1000$， $0 \le K < n$。