Problem F
The Difference Engine
Input: standard input
Output: standard output
Time Limit: 3 seconds

A good way to transmit information over an unreliable connection is to use redundancy to eliminate the damage caused by small errors.  For instance, a checksum on data can be used to reliably determine if a mistake exists anywhere in the data.  And if one byte (anywhere in the data) is missing, the checksum can be used to reconstruct the value of that byte.  We will examine a generalized redundancy approach that allows us to reconstruct a message from which some information has been lost.


Let p be a prime.  Suppose we have a sequence of p "chunks", a1, a2, ..., ap, each with a value between 0 and p-1 inclusive.  We can construct a "difference sequence," b1, b2, ..., bp, which has the same format, and contains the differences between successive elements of a.  (Modular arithmetic is used to

keep the values between 0 and p-1)  So b1 == a2 - a1 (mod p); b2 == a3 - a2 (mod p); and so on, wrapping around to give bp == a1 - ap (mod p).


We can take the difference sequence of this difference sequence to get a "2nd difference sequence".  In general, let the "nth difference sequence" be the result of applying this operation to a sequence n times.


Not every sequence can be an "nth difference sequence", so such a sequence is redundant in a very useful way.  If somebody tells you they have a message (a sequence of this form) that IS an nth difference sequence, and sends it to you, you can reconstruct their message even if up to n "chunks" are lost along the way.  It is straightforward to encode useful information this way: you can write p-n "chunks" of information, then add n "chunks" to make the sequence an nth difference sequence (of some unimportant initial sequence).


Write a program to reconstruct messages of this form.



There will be up to 100 cases, each consisting of two lines.  The first line contains p, a prime number less than 100, and n, a positive integer.  The second line contains p integers from 0 to p-1, containing the message; however, up to n of them may be missing, and will be replaced by question marks.


Input is terminated by a line containing two zeros.



For each case, output one line containing the reconstructed message, which will be an "nth difference sequence".  If this is impossible, output "Invalid message!".


Sample Input                           Output for Sample Input

5 1
1 3 4 ? 3
5 1
1 3 4 2 3
0 0

1 3 4 4 3

Invalid message!

Problem setter: Derek Kisman, EPS