A transmitter sends over a noisy line some binary code words. The receiver on the other end uses a special technique to recover the original words.
Every word originally consists of symbols 0 and 1. All words have the same length N
(4 ≤ N
≤ 1000). After traveling through the noisy line one (but no more) of the following modifications to a word may occur:
- Any (but only one) symbol 0 is replaced by 1.
- Any (but only one) symbol is removed.
- A symbol (0 or 1) is inserted at any position.
It is known that the original words all have the following property: the sum of positions where symbols 1 are located is a multiple of (N+1) or equal to zero.
Input contains number N followed by received words. The words are delimited with line breaks. There will be no more than 2001 words. There is nothing else in the input data, except maybe for some extra spaces or line breaks.
Your program should print to output the original sequence of words as they were transmitted. The words should be delimited by line breaks.
Problem Source: USU Championship 1997