Checksum

A checksum detects errors that occur when data is transmitted or entered. Many algorithms have been invented for this purpose. This problem covers one of the simplest.

The checksum of a number sequence $(A_1, A_2, \ldots)$ is

$(A_1 \cdot K_1 + A_2 \cdot K_2 + \ldots + A_N \cdot K_N + A_{N+1} \cdot K_1 + \ldots) \bmod 10$

where $K_1, K_2, \ldots, K_N$ are fixed constants. The sequence $K$ is treated as periodic. If $A$ is longer than $K$, the elements of $K$ are used again from the beginning. If $A$ is shorter, some elements of $K$ are not used.

Juku found a system that uses this checksum. He does not know the length $N$ of the sequence $K$ or the values $K_i$. He only knows that $N \le 1\,000$ and $1 \le K_i \le 9$. Juku can send queries to the system. Each query is a number sequence, and the system returns its checksum. The 0 key on Juku's keyboard is slightly broken, so 0 is hard to type. For this reason, he wants to avoid the digit 0 in his queries.

Write a program that finds the length of the sequence $K$ and the values of its elements. Since $K$ is periodic, there are infinitely many possible answers. Output the shortest one.