题目描述
Problem Description
Deidra is performing columnar addition. She writes down two positive integers, aligning them one below the other and padding them with leading zeros so they have the same length, then calculates their sum (e.g., $77 + 05 = 82$). If the result's length exceeds that of either summand due to carry (e.g., $96 + 07 = 103$), she prepends zeros to both summands ($096 + 007 = 103$). She allows unnecessary leading zeros as long as all three numbers have the same length (e.g., $007 + 004 = 011$).
Deidra also has a homemade printer. She decided to print her addition without a plus sign or a horizontal line, using the following standard font:
Unfortunately, she messed up the spacing, and all digits were printed overlapping each other. Digits meant to be horizontally adjacent were printed such that the right two segments of the left digit coincide with the left two segments of the right digit. Vertically adjacent digits were printed such that the bottom half (a square with four segments) of the upper digit coincides with the top half of the lower digit.
When one or more black segments are printed at the same position, it appears black. When only empty segments are printed at the position, it appears white.
Given a resulting image, find a correct addition that could produce it or determine that there is none.
Input Format
The first line contains an integer $w$ ($1 \le w \le 100$), representing the width of Deidra's addition (number of digits in each line).
The following $9$ lines describe the image printed with incorrect spacing. Each line contains $w$ or $w+1$ digits. "1" denotes a black segment, and "0" denotes a white segment. Even lines start with a space. Refer to the samples for clarification.
Output Format
If there is no valid addition, output NO.
Otherwise, output a valid addition that produces the given image. The output should consist of three lines, each containing $w$ digits.
If there are multiple solutions, output any one of them.
Sample Input and Output
Input Sample #1
2
1 1
0 1 1
1 0
0 1 1
1 1
0 1 1
1 0
0 1 1
0 0
Output Sample #1
37
34
71
Input Sample #2
1
1
0 1
1
1 1
1
1 1
1
0 1
0
Output Sample #2
2
2
4
Input Sample #3
1
1
1 0
1
1 1
1
1 1
1
0 1
0
Output Sample #3
NO
Notes/Hints
Time limit: 2 seconds, Memory limit: 256 MB.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分