Divisor Subsequence Series

Time limit2sMemory limit128 MB

Summary

Given N, repeatedly delete digits forming a proper divisor subsequence to build the longest possible chain, breaking ties lexicographically smallest.

Level: Hard8 of 10
Topics: Backtracking, Greedy, Dynamic programming, Number theory
Solved: No attempts yet

Problem

You are given a positive integer N.

For the current number X, choose some but not all digit positions from its decimal representation, preserving their order. The chosen digits form a divisor subsequence if the resulting number is greater than 1, does not start with 0, and divides X exactly.

In one step, delete the digit positions of one divisor subsequence from X. Concatenate the remaining digits in their original order, then remove all leading zeros to obtain the next number. If every remaining digit is 0, the next number is 0.

Repeat this process until no next number can be made, producing X1, X2, ..., Xk. Your goal is to maximize k. If several sequences have the same maximum length, compare X2, then X3, and so on; choose the sequence whose first differing number is smaller.

Input

The first line contains a positive integer N.

1 <= N <= 1,000,000,000

Output

Print all numbers in the chosen sequence on one line, separated by spaces.

Examples2

Example 1
Input
```
8013824
```
Expected output
```
8013824 13824 1324 132 12 1
```
Example 2
Input
```
7457762
```
Expected output
```
7457762 5772 77 7
```