In many problems where the lexicographically smallest solution is sought, an algorithm can be formed if the following question can be answered: "Suppose I have this partial solution. Is it possible to extend to make a complete solution?" In this problem, it would mean that a certain number of cells have been filled (and part of the letters used) and we want to know if it is possible to fill the rest of the matrix (so that it is symmetric).

If we can answer this question, then we can fill the cells in order and, for each cell, consider putting letters in it in increasing order: "If I put the letter A, will I be able to complete the matrix? No? What if I put the letter B?" etc. This is an example of a greedy algorithm, taking advantage of the fact that for lexicographical order it is always better to put smaller letters as early as possible.

How to answer the question? For the matrix to be symmetric, cells other than ones on the diagonal must be paired. In other words, for every cell above the diagonal, the corresponding cell below the diagonal must contain the same letter. In even more words, letters we can't pair up must go on the main diagonal. Of the ~26~ letters possibly available to us, the number of those available in odd quantities must not be greater than the number of cells on the diagonal, because we can't pair up those odd letters.

Any implementation of this idea and complexity ~\mathcal O(N^2)~ should have scored ~60\%~.

For ~80\%~ an efficient implementation was needed, with lower constant factors. It is interesting that a solution that uses less memory (i.e. doesn't build the entire matrix then outputs part of the columns, but keeps only needed columns) is noticeably faster in practice.

For full points, by analyzing the first algorithm deeper, we can observe that, within a single row, we often place the same letter in large blocks. Two types of events can interrupt this block-filling:

1. We run out of the letter we are filling with.
2. We run into a column that needs to be output.

Using this approach, the number of steps in our algorithm is proportional to ~N \cdot (P+26)~.