Десятковий#2653

Десятковий

4 секунди

64 мегабайти

Середня

Раціональне число — це число, яке можна подати у вигляді відношення двох цілих чисел. Крім того, усі раціональні числа можна записати десятковим дробом з періодичною (що повторюється) частиною (у деяких випадках повторюваною частиною є $0$ ). Наприклад, $1/7 = 0.1428571428571428 \dots$ 1/7 = 0.1428571428571428\ldots, при цьому $142857$ повторюється нескінченно. Деякі дроби мають скінченну кількість цифр перед початком періодичної частини. Наприклад, $1/6 = 0.166666 \dots$ 1/6 = 0.166666\ldots починається з $1$ , після чого повторюється $6$ .

Ваше завдання — написати програму, яка приймає чотири цілі числа: $l o w er$ , $u pp er$ , $l o w er L e n g t h$ lowerLength та $u pp er L e n g t h$ upperLength. Ваша програма повинна знайти всі цілі числа $n$ від $l o w er$ до $u pp er$ (включно), такі, що періодична частина десяткового подання числа $1/ n$ має кількість цифр від $l o w er L e n g t h$ lowerLength до $u pp er L e n g t h$ upperLength (включно). Потрібно вивести кількість таких чисел, а також їх у порядку зростання.

Вхідні дані

У першому рядку задано ціле число $l o w er$ ( $1 \leq l o w er \leq 1000000$ 1 \leq lower \leq 1000000). У другому рядку задано ціле число $u pp er$ ( $1 \leq u pp er \leq 1000000$ 1 \leq upper \leq 1000000). Різниця між $u pp er$ та $l o w er$ буде не більшою за $100$ .

У третьому рядку задано ціле число $l o w er L e n g t h$ lowerLength ( $1 \leq l o w er L e n g t h \leq 1000000$ 1 \leq lowerLength \leq 1000000). У четвертому рядку задано ціле число $u pp er L e n g t h$ upperLength ( $1 \leq u pp er L e n g t h \leq 1000000$ 1 \leq upperLength \leq 1000000). $u pp er L e n g t h$ upperLength буде більшим або дорівнюватиме $l o w er L e n g t h$ lowerLength.

Вихідні дані

Виведіть кількість знайдених чисел у першому рядку. Далі виведіть ці числа у порядку зростання, по одному у кожному рядку.

Приклади

Приклад 1