Efficient Lighting Installation

After founding his light bulb company in Eindhoven in 1891, Frederik Philips made a groundbreaking discovery: light bulbs that emit infinite rays of light horizontally or vertically. Inspired by this, he and his son Gerard planned a complex installation in a room arranged as an \(N \times N\) grid. Each cell in the grid contains a bulb that, when turned on, lights up either its entire row (if the bulb is oriented horizontally) or its entire column (if oriented vertically).

Unfortunately, during installation, the orientations of the bulbs were not recorded. Instead, experiments were performed: in each experiment, a configuration is chosen (a grid of 0s and 1s, where 1 indicates a turned on bulb) and the number of lit cells is reported. A lit cell is one that is illuminated by at least one bulb – even if multiple bulbs light the same cell, it is counted only once.

Your task is to determine, with as few experiments as possible (at most 2000), which bulbs to turn on so that the entire room is lit while using the minimum number of bulbs. When you have determined the optimal configuration, you should output your final answer in the required format. The interactive protocol is as follows:

• First, your program reads an integer \(N\), the grid dimensions.
• To perform an experiment, output a line with a question mark ? followed by \(N\) lines each containing an \(N\)-character string of 0s and 1s. Then read an integer \(l\) (\(0 \le l \le N^2\)), which is the number of lit cells for that configuration.
• When you are ready to answer, output an exclamation mark ! followed by \(N\) lines describing your final configuration. The final configuration must guarantee that every cell is lit and the number of bulbs turned on is minimal.

Important: In our offline simulation, after \(N\) the input will consist of \(N\) lines, each a string of length \(N\) made up of characters H and V that denote the fixed orientations of the bulbs (Horizontal and Vertical respectively). Using this information, you must compute the minimal valid configuration. Note that when a horizontal bulb is turned on, it lights its entire row, and when a vertical bulb is turned on, it lights its entire column.

Hint: A valid strategy is to choose exactly one bulb in each row or one bulb in each column (depending on the configuration) so that for every cell \((i,j)\) either row \(i\) is lit by a horizontal bulb or column \(j\) is lit by a vertical bulb. In many cases, the optimal solution uses exactly \(N\) bulbs.

inputFormat

The interactor first provides an integer \(N\) — the grid size. In our offline simulation, the next \(N\) lines each contain a string of length \(N\) consisting of the characters H (horizontal) and V (vertical), representing the fixed orientations of the bulbs in each cell.

outputFormat

When performing an experiment, first output a line with a question mark ? followed by \(N\) lines where each line is an \(N\)-character string of 0s and 1s indicating which bulbs are turned on. When outputting your final answer, print a line with an exclamation mark ! followed by \(N\) lines in the same format. The final configuration must light the entire grid and use as few bulbs as possible.

sample

2
HV
HH

!
10
10