2835：Sunzi's Problem

In the ancient work Sunzi Suanjing (Master Sun’s Mathematical Manual), the problem below was mentioned.

“We have a number of things, but we do not know exactly how many. If we count them by threes we have two left over. If we count them by fives we have three left over. If we count them by sevens we have two left over. How many things are there?”

Sunzi wrote in his work, “The answer is twenty-three.”

In 1592, Dawei Cheng put the solution to the problem as a poem in Suanfa Tongzong (Systematic Treatise on Arithmetic).

“Three septuagenarians walking together, ’tis rare!
“Five plum trees with twenty one branches in flower,
“Seven disciples gathering right by the half-moon,
“One hundred and five taken away, lo the result shall appear!”

In modern notation, Sunzi’s problem is to find a number x such that

x ≡ 2 (mod 3),
x ≡ 3 (mod 5),
x ≡ 2 (mod 7).

And Cheng’s solution is

x ≡ 2 × 70 + 3 × 21 + 2 × 15 ≡ 233 (mod 105).

The solution also indicates that if one is given three integers r₁, r₂, r₃ and is asked to find a number x such that

x ≡ r₁ (mod 3),
x ≡ r₂ (mod 5),
x ≡ r₃ (mod 7),

then the answer is

x ≡ r₁ × 70 + r₂ × 21 + r₃ × 15 (mod 105).

For example, for r₁ = 1, r₂ = 4, r₃ = 4, the answer is

x ≡ 1 × 70 + 4 × 21 + 4 × 15 ≡ 214 (mod 105).

In generalization, given n positive integers a₁, a₂, …, a_n, the problem is to determine whether there exist n positive integers b₁, b₂, …, b_n such that for any positive integer N, let p_i (1 ≤ i ≤ n) be the remainder of N taken modulo a_i and M = p₁ × b₁ + p₂ × b₂ + … + p_n × b_n, then M ≡ p_i (mod a_i) for all i (1 ≤ i ≤ n); and to find a set of values of b₁, b₂, …, b_n if they exist.

The input consists of multiple test cases. Each test case is given in one line. In each test case, given first is the integer n (1 ≤ n ≤ 10), which is followed by a₁, a₂, …, a_n (a_i ≤ 50, 1 ≤ i ≤ n). The last case, with n = 0, indicates the end of input and should not be processed.

For each test case, output one line. If the positive integers b₁, b₂, …, b_n exist, output them (none of them should be longer than 50 decimal digits) separated by single spaces. If there are multiple answers, output any one. Output “NO” if they do not exist.

Mind your program’s output format since special judge is used.