Problem Description

Xiao Lu has a positive integer \( n \). He performs several operations as follows:

• Extract the last digit of the positive integer \( n \), denoted as \( x \);
• Square \( x \) and keep only the last digit, then place it before the first digit of \( n \) (if it is \( 0 \), do not keep leading zeros);

These two steps together constitute one operation. For example, for a positive integer \( 142 \), it can undergo the following operations:

• Extract the last digit \( 2 \), the original positive integer becomes \( 14 \);
• \( 2^2 = 4 \), place \( 4 \) before the first digit of \( 14 \) to become \( 414 \), the first operation is completed;
• Extract the last digit \( 4 \), the original positive integer becomes \( 41 \);
• \( 4^2 = 16 \), keep the last digit \( 6 \), place it before the first digit of \( 41 \) to become \( 641 \), the second operation is completed;
• And so on...

Now, Xiao Lu wants to know if a positive integer \( n \) can be transformed into a positive integer \( m \) through no more than \( q \) operations. Please help him.

Input Format

Input consists of three positive integers \( n, m, q \).

Output Format

If it is possible to transform the positive integer \( n \) into the positive integer \( m \) through no more than \( q \) operations, output several lines, with the \( i \)-th line outputting a positive integer representing the value of \( n \) after the \( i \)-th operation. Otherwise, output a single line with the integer \(-1\).

Sample Input and Output

Sample Input #1

123 611 10

Sample Output #1

912
491
149
114
611

Sample Input #2

123 231 12345

Sample Output #2

-1

Notes

For \( 30\% \) of the data, it is guaranteed that Xiao Lu can obtain \( m \) with no more than \( 5 \) operations;

For all data, it is guaranteed that \( 1 \leq n, m \leq 10^9 \) and \( 1 \leq q \leq 10^6 \).

见题面 Input 部分

见题面 Output 部分