It is well known that while squares are bad, arithmetic is even worse for the mental health of highschool age children doing programming contests. For this reason, Lakshy's CCC (Competitive Computing Contest) mental health break entails the Palindromic Rectangle problem.
Given an ~N \times M~ matrix of cells which either already contain a lowercase letter or are empty, determine values for each empty cell such that every row and column forms a palindrome.
Recall that a palindrome is a sequence of characters that reads the same backwards as forwards.
While Lakshy could totally do the problem himself, he is too busy struggling to read his poorly written IB HL chemistry notes. He leaves the task to you. Please write a program to help him solve the problem!
~1 \le N, M \le 2 \times 10^3~
Subtask 1 [10%]
~N = M = 3~
Subtask 2 [90%]
No additional constraints.
The first line will contain two integers ~N~ and ~M~, the number of rows and columns of the grid, respectively.
The next ~N~ lines will each contain ~M~ characters, representing the rows of the grid. Each character will either be a lowercase letter, or the symbol
., which indicates that the value is unspecified.
If no solution exists, output
Otherwise, output ~N~ lines consisting of ~M~ lowercase letters each, the correctly filled-in grid. Any valid solution will be accepted.
Sample Input 1
3 3 iii ooo ...
Sample Output 1
iii ooo iii
Explanation for Sample 1
All of the rows (
iii) and all of the columns (
ioi) form palindromes, so the solution is correct.
Sample Input 2
1 33 ccchasbecome........inrecentyears
Sample Output 2
Explanation for Sample 2
It can be shown that there is no way to fill the empty grid cells such that the first row of the grid forms a palindrome, therefore a solution is impossible.