Grid Infection with Recovery After D Days

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

Grid Infection with Recovery After D Days (Become Immune)

Building on (2), add recovery:

Each infected cell 'X' recovers after D days since it got infected and becomes immune 'I' at the end of that day.

Immune 'I' can never be infected and does not infect others.

A healthy '.' becomes infected 'X' at the end of a day if it has at least T infected 'X' neighbors among its 8 neighbors.

Return the number of days until the grid becomes stable, defined as: there are no infected 'X' cells left.

Updates are synchronous. You must track infection age per cell.

Example

Input

3 3

1 1

.X.

...

Output

2

Complete solveGridInfectionRecoveryAfterDays. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.