a052. 一次性訊號站

題目敘述

防災中心正在測試一套緊急訊息傳遞系統。城市裡的訊號站整齊排列成 M 列、N 行，當某座訊號站發出訊息時，與它相鄰的待命訊號站就能接收訊息，並在下一秒接力發送。這套系統使用的是一次性設備：每座訊號站只要完成發送，就會永久停用，無法再次啟動。

為了追蹤訊息的傳遞情形，防災中心把每座訊號站的狀態記錄在一個格子中。每個格子都有以下三種狀態之一：

• 0：停用，無法發送訊號。
• 1：待命，尚未發送訊號。
• 2：正在發送訊號。

系統每過一秒會更新一次。所有訊號站同時更新，每座訊號站的下一個狀態，只能依照更新前的狀態來決定，規則如下：

1. 正在發送的訊號站（2）完成發送後，變成停用（0）。
2. 待命的訊號站（1）會檢查上、下、左、右四個相鄰位置。如果其中至少有一座訊號站目前正在發送（2），這座待命站就會在下一秒開始發送，變成 2；否則維持 1。
3. 停用的訊號站（0）維持停用。

只有共用一條邊的格子才算相鄰，斜對角不算；超出城市範圍的位置也不存在。停用站既不會發送訊號，也不會因為附近有其他站正在發送而重新啟動。

請根據初始狀態，求出經過 T 秒後，所有訊號站的狀態。如果 T = 0，直接輸出初始狀態。

輸入格式

第一行有三個整數 M、N、T，分別代表訊號站的列數、行數及經過的秒數。

接下來 M 行，每行有 N 個整數，代表訊號站的初始狀態。每個整數皆為 0、1 或 2，同一行相鄰兩數以一個空白分隔。

限制

• 1 ≤ M, N ≤ 100
• 0 ≤ T ≤ 100

子題

• 子題一（60 分）：M = 1。
• 子題二（40 分）：無額外限制。

輸出格式

輸出經過 T 秒後的狀態，共 M 行，每行 N 個整數，相鄰整數以一個空白分隔。

範例一

範例輸入：

1 6 3
1 1 1 2 0 1

範例輸出：

2 0 0 0 0 1

一開始，從左數第四座站正在發送。每秒結束後，各站的狀態依序如下：

• 第 1 秒：1 1 2 0 0 1。第四座站停用，第三座站開始發送。
• 第 2 秒：1 2 0 0 0 1。訊號繼續往左傳遞。
• 第 3 秒：2 0 0 0 0 1。

第五座站一開始就已停用，無法把訊號傳給最右側的待命站，因此最右側始終維持 1。

範例二

範例輸入：

3 4 2
1 1 0 1
1 2 1 1
0 1 1 2

範例輸出：

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

第 1 秒後的盤面為：

1 2 0 1
2 0 2 2
0 2 2 0

原本正在發送的兩座站已停用，與它們相鄰的待命站開始發送。第 2 秒更新時，第一列最左邊和最右邊的待命站，分別因為下方有正在發送的站而開始發送；第 1 秒才開始發送的站則全部停用。注意每一秒都要先看完整的舊盤面，不能讓同一秒剛開始發送的站立刻影響其他站。