P1942 Word Encoding

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$.

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$.

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$.

Translated by ChatGPT 5