Description
In a place far, far away, there was a peaceful town known as The Kingdom of Ingridus whose town map can be represented as a grid where each cell in the grid corresponds to a house. The villagers were living in harmony until one day, the beloved King Domov Ingridus passed away, and his three sons—Prince Rock, Prince Scissors, and Prince Paper—began vying for the throne. Unable to decide who should be the new king, they used the villagers to determine the "rightful" ruler.
On the first day, they announced that all villagers must display the royal symbol of their preferred candidates—Rock, Scissors, and Paper—in front of their houses. However, the villagers of the Kingdom of Ingridus aren't very decisive about their choices. Every day, they change their choices based on the preferences of their neighbors (the cells directly adjacent horizontally, vertically, or diagonally to them) according to certain rules, that is:
- If the majority of their neighbors display a rock symbol, they will display a paper symbol the next day.
- If the majority of their neighbors display a paper symbol, they will display a scissors symbol the next day.
- If the majority of their neighbors display a scissors symbol, they will display a rock symbol the next day.
- If there is a tie, they keep their current symbol.
For example, suppose the original voting result looks like this:
The majority vote of each cell's neighbors will look like this:
The number here represents the majority vote, while the dash symbolizes a tie. For example, the gap between I and 2 on the bottom line has the rock sign but is surrounded by three papers and two rocks (excluding itself), so the majority vote of its neighbor is labeled 5 (paper) here. According to the rules, the sign should be changed to scissors. Considering the whole grid, the result the following day would be:
The election was conducted by counting the symbols D day afterward. However, it had been a few thousand years since that time, and all the records but one were burned at the order of an unnamed emperor. As an aspiring historian, you want to know what happened and are determined to recover the true outcome of the ancient election, shedding light on the lost kingdom's history. Therefore, you decide to take a methodical approach to recover the true outcome of the ancient election.
For your reference, this is the change in case D = 7.
Clarification:
For your reference, here are the images of grids on different days. Sorry for the inconvenience.
| Day | Unlabeled Grid | Majority Vote for the next day |
| 1 |  |
 |
| 2 |  |
 |
| 3 |  |
 |
| 4 |  |
 |
| 5 |  |
 |
| 6 |  |
 |
| 7 |  |
None (Voting ended on the 7th day) |
Input
The first line contains three integers: H, W, and D. (1 ≤ H, W ≤ 256; 1 ≤ D ≤ 7)
The next H lines each contain W integers representing the initial state of the grid. Each integer is either 0, 2, or 5, representing rock, scissors, and paper respectively.
Output
The final state of the grid. Each row of the grid should be printed on a new line, with each cell's value being either 0, 2, or 5 followed by a space.