A number is said to be stable if the difference between every two continuous digits is not greater than 1. For example, 12345, 54565 are stable numbers, while 13456 is not (because |1-3|=2>1).

Given two positive integers a,b. Your task is:

- Caculate the number (M) of stable numbers C that A<C<B.

- If there are M stable numbers C₁,C₂,...,C_M that A<C₁<C₂<...<C_M<B; find C_(M+1)/2 if M is odd, or C_M/2, C_M/2+1 if M is even.

Input

Two numbers a,b on the first line. A number q on the second line.

Output

If q=1, write the number of stable numbers (M) (in one line).

if q=2, write the number(s) needed to be found (in one line, a space between two numbers).

Example

Input 1:
1 22

1
Output 1:
12

Input 2:

1 22

2

Output 2:

7 8

Input 3:

90 111

2

Output 3:

100

Explanation for example 1 and 2: There are 12 stable numbers: 2,3,4,5,6,7,8,9,10,11,12,21

Constrains

0<A<B<10¹⁸

0<q<3