Digital Root Decryption

MCPlayer542 holds a mysterious prime p but does not want to reveal it. Instead, he encrypts a number using a modified digit‐sum function. Let \(f(x)\) be the function that returns the sum of the digits of \(x\) in its decimal representation (for example, \(f(542)=5+4+2=11\)). He then applies this function 10 times to define \(g(x)=f(f(\cdots f(x)\cdots))\) (10 times in total). Next, he computes \(q=p^k\) (for some positive integer \(k\)), and provides you with \(n\) integers: \(g(q^{a_1}), g(q^{a_2}), \ldots, g(q^{a_n})\).

You are allowed to choose the modulus parameter \(m\) and the exponents \(a_1, a_2, \ldots, a_n\) with a special restriction on \(m\) such that for every query \(m \times a_i = 9\). Under this condition, the digital root property implies that \[ q^{a_i} \bmod (m\cdot a_i) = q^{a_i} \bmod 9, \] which is exactly the value of \(g(q^{a_i})\) (taking into account that if \(q^{a_i}\) is divisible by 9, the digital root is 9 instead of 0).

Your task is simple: given \(m\), \(n\), and the sequence of numbers \(g(q^{a_1}),\ g(q^{a_2}),\ \ldots,\ g(q^{a_n})\), output the sequence \[ q^{a_1} \bmod (m\cdot a_1),\ q^{a_2} \bmod (m\cdot a_2),\ \ldots,\ q^{a_n} \bmod (m\cdot a_n). \]

Note: Due to the special restriction, it is typically the case that you have chosen \(m\) and \(a_i\) so that \(m\cdot a_i = 9\) (for example, \(m=9, a_i=1\); \(m=3, a_i=3\); or \(m=1, a_i=9\)). In these cases, the answer is exactly \(g(q^{a_i})\) for each \(i\).

inputFormat

The first line contains two integers \(m\) and \(n\) separated by a space. The second line contains \(n\) integers: \(g(q^{a_1}), g(q^{a_2}), \ldots, g(q^{a_n})\), separated by spaces.

Constraints: It is guaranteed that the chosen values satisfy the special condition \(m \times a_i = 9\) for every \(i\).

outputFormat

Output a single line with \(n\) integers separated by spaces, where the \(i\)-th integer is \(q^{a_i} \bmod (m \cdot a_i)\). Under the condition \(m \times a_i = 9\), this is equal to \(g(q^{a_i})\) for each \(i\).

sample

9 3
7 9 4

7 9 4