在神秘的 Aethergrid 领域，土地由 $N$ 行 $M$ 列交织而成。该网格中的每个单元格都可以呈现以下魔法形态之一：
- 黑曜石结界（Obsidian Ward），用
#表示，是无法逾越的坚固魔法屏障。 - 以太通道（Ethereal Passage），用
.表示，是一条供敢于冒险之人自由通行的开放路径。 - 星空枢纽（Celestial Nexus），用
C表示，泡泡机器人（Bubble Bot）可以在此汲取古老能量，将电量恢复至满格。
泡泡机器人从某个特定的以太通道或星空枢纽开始其旅程，并且可以通过单步移动到四个相邻单元格（东、南、西、北）中的任意一个。每移动一步都会消耗其奥术电池的一格电量。在能量耗尽之前，泡泡机器人最多可以移动 $K$ 步。踏上星空枢纽会立即将其电池充满至最大容量，使其能够继续探索。不允许踏上黑曜石结界。
你的任务是，对于每个可能的起点单元格，确定泡泡机器人从其初始单元格出发所能到达的最远曼哈顿距离。如果起点是黑曜石结界，则最大距离视为 $-1$。
位于 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的两个单元格之间的曼哈顿距离计算为 $|x_1 - x_2| + |y_1 - y_2|$，这是空间邻近度的神圣计算方式。请注意，此距离计算忽略所有黑曜石结界。
输入格式
第一行包含三个整数 $N$、$M$ 和 $K$：分别表示网格的行数、列数，以及泡泡机器人在需要充电前最多可以移动的步数（$1 \le N, M, K \le 300$）。
接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，表示网格。每个字符要么是表示以太通道的 .，要么是表示黑曜石结界的 #，要么是表示星空枢纽的 C。
输出格式
输出 $N$ 行，每行包含 $M$ 个空格分隔的整数。对于网格中的每个单元格，如果该单元格是黑曜石结界，则输出 $-1$；否则，输出在遵守移动和充电限制的情况下，泡泡机器人从该起点出发所能到达的单元格与起点的最大曼哈顿距离。
样例
输入样例 1
3 3 1 ... #C# .C.
输出样例 1
1 3 1 -1 2 -1 3 2 3
说明
设 $(R, C)$ 表示第 $R$ 行第 $C$ 列的单元格。在样例中，泡泡机器人从每个起点出发所能到达的最远单元格如下：
- 从单元格 $(1, 1)$ 和 $(1, 3)$ 出发，在电量耗尽前能到达的最远单元格是 $(1, 2)$。
- 从单元格 $(2, 2)$ 出发，在此过程中使用两个充电器，能到达的最远单元格之一是 $(3, 1)$。
- 从单元格 $(3, 1)$ 和 $(3, 3)$ 出发，在电量耗尽前能到达的最远单元格是 $(1, 2)$。
- 从单元格 $(3, 2)$ 出发，能到达的最远单元格是 $(1, 2)$。
- 从单元格 $(1, 2)$ 出发，能到达的最远单元格是 $(3, 1)$ 和 $(3, 3)$。