SquareCode

When Bob learned that he was to be sent abroad to work on an oil rig, he resolved that he would write regularly to his girlfriend.

"We'll have to encrypt our correspondence," he told Alice, "so that my tender feelings remain unknown to the rest of the crew."

Alice showed Bob a simple kind of text encryption that makes use of a square cardboard grille divided into equal-sized cells, exactly one quarter of which are punched out to make holes. For example, a six-by-six grille might be configured as follows, where '.' stands for a hole and 'X' for a cell that has been left intact.

               XXXXXX
               .XXXX.
               X.XX..
               XXX.XX
               X.XXXX
               XX.XX.

To encrypt a message, Bob begins writing plaintext into the grille, one character per hole, proceeding from left to right within each row and running through the rows from top to bottom. Once all holes are filled, he rotates the grille ninety degrees clockwise, and continues the message where he left off. After two more quarter turns, he has written a full square of coded text, and must begin a new one. Upon receipt of the message, Alice uses an identical grille to decrypt each square. If, for example, Bob's plaintext were "supercalifragilisticexpialadociously", Alice would receive the following code.

               idocfc
               sriaeu
               gpxoer
               piicau
               laslla
               iylsti

Not just any grille will do for this purpose, as Bob discovered when he tried to make one by cutting out holes at random. He found that this haphazard grille wouldn't let him write out a full square of text in the prescribed manner. After fewer than four quarter-turns, some holes revealed previously written characters. Alice assured him that this was a grave flaw. An encoding grille must permit one to fill the entire square by making three quarter-turns, and it must show each cell of the square exactly once. Bob, alas, had a lyrical soul and not a mathematical one. He could not perceive the properties that make a grille suitable for use with this encryption technique. Can you?

You are given a String[] describing a grille row by row, in the style shown above, with no more than a quarter of its holes punched out. If it is not possible to make a complete and valid encoding grille from this configuration by punching out zero or more additional holes, then return an empty String[]. Otherwise, punch out the necessary holes in the upper-left quadrant to make a complete and valid grille, and return it in the same format as the input.