시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 13 5 4 40.000%

문제

한 수열의 부분수열은 주어진 수열에서 몇 개의(1개 이상) 숫자를 제거하여 얻어진 수열을 말한다. 이때 제거하는 수들이 꼭 연속적일 필요는 없다. 예를 들어 1234의 부분수열로는 1, 2, 12, 13, 24 등이 있지만, 1234는 제거한 숫자가 없으므로 부분수열이 아니다.

약수부분수열이란, 부분수열이 나타내는 수가 동시에 약수인 것을 의미한다. 예를 들어 8013824의 약수부분수열로는 8, 13, 14 등이 있다.

입력으로 한 자연수 N이 주어졌을 때, N에서 약수부분수열을 하나 제거해 다음 수 N[2]를 만든다. 이 N[2]에서 약수부분수열을 또 하나 제거하면 N[3]를 만들 수 있고, N[3]에서 약수부분수열을 또 하나 제거하면 N[4]를 만들 수 있다. 이와 같은 과정을 더 이상 다음 수를 만들 수 없을 때까지 반복하면 N, N[2], …, N[k]와 같은 수열을 얻을 수 있다. 이때 k를 최대로 하려고 한다.

8013824와 같은 경우에는 약수부분수열 80을 제거하여 N[2]=13824을 얻고, N[3]=1324,  N[4]=132, N[5]=12, N[6]=1을 얻는다. 이때 k=6이 되고, 이 경우가 k가 제일 커지는 경우이다.

입력

첫째 줄에는 자연수 N(1≤N≤1,000,000,000)이 주어진다.

출력

첫째 줄에 차례로 N, N[1], N[2], …, N[k]를 출력한다.

예제 입력 1

8013824

예제 출력 1

8013824 13824 1324 132 12 1
W3sicHJvYmxlbV9pZCI6IjIzNjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCgxXHVhYzFjIFx1Yzc3NFx1YzBjMSkgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YzVlYyBcdWM1YmJcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHVhZjJkIFx1YzVmMFx1YzE4ZFx1YzgwMVx1Yzc3YyBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDEyMzRcdWM3NTggXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHViODVjXHViMjk0IDEsIDIsIDEyLCAxMywgMjQgXHViNGYxXHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgMTIzNFx1YjI5NCBcdWM4MWNcdWFjNzBcdWQ1NWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YyBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcbjxwPlx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc3NFx1Yjc4MCwgXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMThcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzU3ZFx1YzIxOFx1Yzc3OCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDgwMTM4MjRcdWM3NTggXHVjNTdkXHVjMjE4XHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHViODVjXHViMjk0IDgsIDEzLCAxNCBcdWI0ZjFcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWQ1NWMgXHVjNzkwXHVjNWYwXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgTlx1YzVkMFx1YzExYyBcdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NDQgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU3NCBcdWIyZTRcdWM3NGMgXHVjMjE4IE5bMl1cdWI5N2MgXHViOWNjXHViNGUwXHViMmU0LiBcdWM3NzQgTlsyXVx1YzVkMFx1YzExYyBcdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NDQgXHViNjEwIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQgTlszXVx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgTlszXVx1YzVkMFx1YzExYyBcdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NDQgXHViNjEwIFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQgTls0XVx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjZmNcdWM4MTVcdWM3NDQgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWIyZTRcdWM3NGMgXHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMThcdWJjZjVcdWQ1NThcdWJhNzQgTiwgTlsyXSwgJmhlbGxpcDssIE5ba11cdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjIGtcdWI5N2MgXHVjZDVjXHViMzAwXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+ODAxMzgyNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNCA4MFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWM1ZWMgTlsyXT0xMzgyNFx1Yzc0NCBcdWM1YmJcdWFjZTAsIE5bM109MTMyNCwmbmJzcDsgTls0XT0xMzIsIE5bNV09MTIsIE5bNl09MVx1Yzc0NCBcdWM1YmJcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YyBrPTZcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHVhYzAwIGtcdWFjMDAgXHVjODFjXHVjNzdjIFx1Y2VlNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IE4oMSZsZTtOJmxlOzEsMDAwLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzI4XHViODQwXHViODVjIE4sIE5bMV0sIE5bMl0sICZoZWxsaXA7LCBOW2tdXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzNjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltYXJ5IFgtU3ViZmFjdG9yIFNlcmllcyIsImRlc2NyaXB0aW9uIjoiPHA+TGV0IG4gYmUgYW55IHBvc2l0aXZlIGludGVnZXIuIEEgZmFjdG9yIG9mIG4gaXMgYW55IG51bWJlciB0aGF0IGRpdmlkZXMgZXZlbmx5IGludG8gbiwgd2l0aG91dCBsZWF2aW5nIGEgcmVtYWluZGVyLiBGb3IgZXhhbXBsZSwgMTMgaXMgYSBmYWN0b3Igb2YgNTIsIHNpbmNlIDUyXC8xMyA9IDQuIEEgc3Vic2VxdWVuY2Ugb2YgbiBpcyBhIG51bWJlciB3aXRob3V0IGEgbGVhZGluZyB6ZXJvIHRoYXQgY2FuIGJlIG9idGFpbmVkIGZyb20gbiBieSBkaXNjYXJkaW5nIG9uZSBvciBtb3JlIG9mIGl0cyBkaWdpdHMuIEZvciBleGFtcGxlLCAyLCAxMywgODAxLCA4ODIsIGFuZCAxMzI0IGFyZSBzdWJzZXF1ZW5jZXMgb2YgODAxMzgyNCwgYnV0IDIxNCBpcyBub3QgKHlvdSBjYW4mIzM5O3QgcmVhcnJhbmdlIGRpZ2l0cyksIDgzMzQgaXMgbm90ICh5b3UgY2FuJiMzOTt0IGhhdmUgbW9yZSBvY2N1cnJlbmNlcyBvZiBhIGRpZ2l0IHRoYW4gYXBwZWFyIGluIHRoZSBvcmlnaW5hbCBudW1iZXIpLCA4MDEzODI0IGlzIG5vdCAoeW91IG11c3QgZGlzY2FyZCBhdCBsZWFzdCBvbmUgZGlnaXQpLCBhbmQgMDEgaXMgbm90ICh5b3UgY2FuJiMzOTt0IGhhdmUgYSBsZWFkaW5nIHplcm8pLiBBIHN1YmZhY3RvciBvZiBuIGlzIGFuIGludGVnZXIgZ3JlYXRlciB0aGFuIDEgdGhhdCBpcyBib3RoIGEgZmFjdG9yIGFuZCBhIHN1YnNlcXVlbmNlIG9mIG4uIDgwMTM4MjQgaGFzIHN1YmZhY3RvcnMgOCwgMTMsIGFuZCAxNC4gU29tZSBudW1iZXJzIGRvIG5vdCBoYXZlIGEgc3ViZmFjdG9yOyBmb3IgZXhhbXBsZSwgNjM0MSBpcyBub3QgZGl2aXNpYmxlIGJ5IDYsIDMsIDQsIDYzLCA2NCwgNjEsIDM0LCAzMSwgNDEsIDYzNCwgNjMxLCA2NDEsIG9yIDM0MS48XC9wPlxyXG5cclxuPHA+QW4geC1zdWJmYWN0b3Igc2VyaWVzIG9mIG4gaXMgYSBkZWNyZWFzaW5nIHNlcmllcyBvZiBpbnRlZ2VycyBuPHN1Yj4xPFwvc3ViPiwgLi4uLCBuPHN1Yj5rPFwvc3ViPiwgaW4gd2hpY2ggKDEpIG4gPSBuPHN1Yj4xPFwvc3ViPiwgKDIpIGsgJmdlOyAxLCAoMykgZm9yIGFsbCAxICZsZTsgaSAmbHQ7IGssIG48c3ViPmkrMTxcL3N1Yj4gaXMgb2J0YWluZWQgZnJvbSBuaSBieSBmaXJzdCBkaXNjYXJkaW5nIHRoZSBkaWdpdHMgb2YgYSBzdWJmYWN0b3Igb2YgbjxzdWI+aTxcL3N1Yj4sIGFuZCB0aGVuIGRpc2NhcmRpbmcgbGVhZGluZyB6ZXJvcywgaWYgYW55LCBhbmQgKDQpIG5rIGhhcyBubyBzdWJmYWN0b3IuIFRoZSB0ZXJtICZxdW90O3gtc3ViZmFjdG9yJnF1b3Q7IGlzIG1lYW50IHRvIHN1Z2dlc3QgdGhhdCBhIHN1YmZhY3RvciBnZXRzIHgmIzM5O2VkLCBvciBkaXNjYXJkZWQsIGFzIHlvdSBnbyBmcm9tIG9uZSBudW1iZXIgdG8gdGhlIG5leHQuIEZvciBleGFtcGxlLCAyMDA0IGhhcyB0d28gZGlzdGluY3QgeC1zdWJmYWN0b3Igc2VyaWVzLCB0aGUgc2Vjb25kIG9mIHdoaWNoIGNhbiBiZSBvYnRhaW5lZCBpbiB0d28gZGlzdGluY3Qgd2F5cy4gVGhlIGhpZ2hsaWdodGVkIGRpZ2l0cyBzaG93IHRoZSBzdWJmYWN0b3IgdGhhdCB3YXMgcmVtb3ZlZCB0byBwcm9kdWNlIHRoZSBuZXh0IG51bWJlciBpbiB0aGUgc2VyaWVzLjxcL3A+XHJcblxyXG48cD48ZW0+PHN0cm9uZz48dT4yPFwvdT48XC9zdHJvbmc+PFwvZW0+MDA0ICZuYnNwOyA0PGJyIFwvPlxyXG4yMDA8dT48c3Ryb25nPjxlbT40PFwvZW0+PFwvc3Ryb25nPjxcL3U+ICZuYnNwOyA8dT48ZW0+PHN0cm9uZz4yMDxcL3N0cm9uZz48XC9lbT48XC91PjAgJm5ic3A7IDA8YnIgXC8+XHJcbjIwMDx1PjxzdHJvbmc+PGVtPjQ8XC9lbT48XC9zdHJvbmc+PFwvdT4gJm5ic3A7IDx1PjxlbT48c3Ryb25nPjI8XC9zdHJvbmc+PFwvZW0+PFwvdT4wMCAmbmJzcDsgMDxcL3A+XHJcblxyXG48cD5UaGUgcHJpbWFyeSB4LXN1YmZhY3RvciBzZXJpZXMgaGFzIG1heGltYWwgbGVuZ3RoICh0aGUgbGFyZ2VzdCBrIHBvc3NpYmxlLCB1c2luZyB0aGUgbm90YXRpb24gYWJvdmUpLiBJZiB0aGVyZSBhcmUgdHdvIG9yIG1vcmUgbWF4aW1hbC1sZW5ndGggc2VyaWVzLCB0aGVuIHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3Qgc2Vjb25kIG51bWJlciBpcyBwcmltYXJ5OyBpZiBhbGwgbWF4aW1hbC1sZW5ndGggc2VyaWVzIGhhdmUgdGhlIHNhbWUgZmlyc3QgYW5kIHNlY29uZCBudW1iZXJzLCB0aGVuIHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3QgdGhpcmQgbnVtYmVyIGlzIHByaW1hcnk7IGFuZCBzbyBvbi4gRXZlcnkgcG9zaXRpdmUgaW50ZWdlciBoYXMgYSB1bmlxdWUgcHJpbWFyeSB4LXN1YmZhY3RvciBzZXJpZXMsIGFsdGhvdWdoIGl0IG1heSBiZSBwb3NzaWJsZSB0byBvYnRhaW4gaXQgaW4gbW9yZSB0aGFuIG9uZSB3YXksIGFzIGlzIHRoZSBjYXNlIHdpdGggMjAwNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBvbmUgb3IgbW9yZSBwb3NpdGl2ZSBpbnRlZ2VycywgZWFjaCBsZXNzIHRoYW4gb25lIGJpbGxpb24sIHdpdGhvdXQgbGVhZGluZyB6ZXJvZXMsIGFuZCBvbiBhIGxpbmUgYnkgaXRzZWxmLiBGb2xsb3dpbmcgaXMgYSBsaW5lIGNvbnRhaW5pbmcgb25seSAmcXVvdDswJnF1b3Q7IHRoYXQgc2lnbmFscyB0aGUgZW5kIG9mIHRoZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcG9zaXRpdmUgaW50ZWdlciwgb3V0cHV0IGl0cyBwcmltYXJ5IHgtc3ViZmFjdG9yIHNlcmllcyB1c2luZyB0aGUgZXhhY3QgZm9ybWF0IHNob3duIGluIHRoZSBleGFtcGxlcyBiZWxvdy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d