Description

A transmitter sends words consisting of $0$ and $1$ through a channel. At the other end, a receiver can use special techniques to recover the original words. Each original word consists only of $0$ and $1$, and every original word has length $n$. After passing through the channel, exactly one of the following may happen to a word:

1. Any single $0$ is replaced by $1$.
2. Any single symbol is deleted.
3. A symbol ($0$ or $1$) is inserted at any position.
4. No change.

We know that every original word has the following property: the sum of the position numbers of the $1$s is a multiple of $n+1$, or equals $0$.

Input Format

The first line contains a positive integer $n\ (4\le n\le 1000)$.

Then follow several lines (not necessarily $\bm n$ lines!), each containing one word after passing through the channel, one word per line.

Please read until the end of file:

• For C++ std::cin, you can use while (std::cin >> s) {/* ... */}, where s is a variable of type std::string.
• For C/C++ scanf, you can use while (scanf("%s", s) == 1) {/* ... */}, where s is a variable of type char*.
• For other input functions, please consult their documentation for how to read until EOF.

It is guaranteed that the number of words does not exceed $2001$.

Output Format

Your program should print the original words, one per line.

If there are multiple valid originals, choose the best one in the following order and output that best one:

• Prefer by operation in the order: operation $4$ → operation $1$ → operation $2$ → operation $3$.
• Within the same operation, prefer the one with the operation position from left to right.
• For operation $3$ inserting at the same position, inserting $0$ is preferred over inserting $1$.

If there is no solution, output $-1$.

4
0000
011
1011
11011

0000
0110
1001
1111

Hint

Translated by ChatGPT 5