시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjIzNjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCgxXHVhYzFjIFx1Yzc3NFx1YzBjMSkgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YzVlYyBcdWM1YmJcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWIyOTQgXHVjMjE4XHViNGU0XHVjNzc0IFx1YWYyZCBcdWM1ZjBcdWMxOGRcdWM4MDFcdWM3N2MgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCAxMjM0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yjg1Y1x1YjI5NCAxLCAyLCAxMiwgMTMsIDI0IFx1YjRmMVx1Yzc3NCBcdWM3ODhcdWM5YzBcdWI5Y2MsIDEyMzRcdWIyOTQgXHVjODFjXHVhYzcwXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMgXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG48cD5cdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NzRcdWI3ODAsIFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM1N2RcdWMyMThcdWM3NzggXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCA4MDEzODI0XHVjNzU4IFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yjg1Y1x1YjI5NCA4LCAxMywgMTQgXHViNGYxXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE5cdWM1ZDBcdWMxMWMgXHVjNTdkXHVjMjE4XHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM4MWNcdWFjNzBcdWQ1NzQgXHViMmU0XHVjNzRjIFx1YzIxOCBOWzJdXHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC4gXHVjNzc0IE5bMl1cdWM1ZDBcdWMxMWMgXHVjNTdkXHVjMjE4XHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjYxMCBcdWQ1NThcdWIwOTggXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IE5bM11cdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIE5bM11cdWM1ZDBcdWMxMWMgXHVjNTdkXHVjMjE4XHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjYxMCBcdWQ1NThcdWIwOTggXHVjODFjXHVhYzcwXHVkNTU4XHViYTc0IE5bNF1cdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YjM1NCBcdWM3NzRcdWMwYzEgXHViMmU0XHVjNzRjIFx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWI1NGNcdWFlNGNcdWM5YzAgXHViYzE4XHViY2Y1XHVkNTU4XHViYTc0IE4sIE5bMl0sICZoZWxsaXA7LCBOW2tdXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMga1x1Yjk3YyBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD44MDEzODI0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTdkXHVjMjE4XHViZDgwXHViZDg0XHVjMjE4XHVjNWY0IDgwXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YzVlYyBOWzJdPTEzODI0XHVjNzQ0IFx1YzViYlx1YWNlMCwgTlszXT0xMzI0LCZuYnNwOyBOWzRdPTEzMiwgTls1XT0xMiwgTls2XT0xXHVjNzQ0IFx1YzViYlx1YjI5NFx1YjJlNC4gXHVjNzc0IFx1YjU0YyBrPTZcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHVhYzAwIGtcdWFjMDAgXHVjODFjXHVjNzdjIFx1Y2VlNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IE4oMSZsZTtOJmxlOzEsMDAwLDAwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzI4XHViODQwXHViODVjIE4sIE5bMV0sIE5bMl0sICZoZWxsaXA7LCBOW2tdXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzNjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmltYXJ5IFgtU3ViZmFjdG9yIFNlcmllcyIsImRlc2NyaXB0aW9uIjoiPHA+TGV0IG4gYmUgYW55IHBvc2l0aXZlIGludGVnZXIuIEEgZmFjdG9yIG9mIG4gaXMgYW55IG51bWJlciB0aGF0IGRpdmlkZXMgZXZlbmx5IGludG8gbiwgd2l0aG91dCBsZWF2aW5nIGEgcmVtYWluZGVyLiBGb3IgZXhhbXBsZSwgMTMgaXMgYSBmYWN0b3Igb2YgNTIsIHNpbmNlIDUyXC8xMyA9IDQuIEEgc3Vic2VxdWVuY2Ugb2YgbiBpcyBhIG51bWJlciB3aXRob3V0IGEgbGVhZGluZyB6ZXJvIHRoYXQgY2FuIGJlIG9idGFpbmVkIGZyb20gbiBieSBkaXNjYXJkaW5nIG9uZSBvciBtb3JlIG9mIGl0cyBkaWdpdHMuIEZvciBleGFtcGxlLCAyLCAxMywgODAxLCA4ODIsIGFuZCAxMzI0IGFyZSBzdWJzZXF1ZW5jZXMgb2YgODAxMzgyNCwgYnV0IDIxNCBpcyBub3QgKHlvdSBjYW4mIzM5O3QgcmVhcnJhbmdlIGRpZ2l0cyksIDgzMzQgaXMgbm90ICh5b3UgY2FuJiMzOTt0IGhhdmUgbW9yZSBvY2N1cnJlbmNlcyBvZiBhIGRpZ2l0IHRoYW4gYXBwZWFyIGluIHRoZSBvcmlnaW5hbCBudW1iZXIpLCA4MDEzODI0IGlzIG5vdCAoeW91IG11c3QgZGlzY2FyZCBhdCBsZWFzdCBvbmUgZGlnaXQpLCBhbmQgMDEgaXMgbm90ICh5b3UgY2FuJiMzOTt0IGhhdmUgYSBsZWFkaW5nIHplcm8pLiBBIHN1YmZhY3RvciBvZiBuIGlzIGFuIGludGVnZXIgZ3JlYXRlciB0aGFuIDEgdGhhdCBpcyBib3RoIGEgZmFjdG9yIGFuZCBhIHN1YnNlcXVlbmNlIG9mIG4uIDgwMTM4MjQgaGFzIHN1YmZhY3RvcnMgOCwgMTMsIGFuZCAxNC4gU29tZSBudW1iZXJzIGRvIG5vdCBoYXZlIGEgc3ViZmFjdG9yOyBmb3IgZXhhbXBsZSwgNjM0MSBpcyBub3QgZGl2aXNpYmxlIGJ5IDYsIDMsIDQsIDYzLCA2NCwgNjEsIDM0LCAzMSwgNDEsIDYzNCwgNjMxLCA2NDEsIG9yIDM0MS48XC9wPlxyXG5cclxuPHA+QW4geC1zdWJmYWN0b3Igc2VyaWVzIG9mIG4gaXMgYSBkZWNyZWFzaW5nIHNlcmllcyBvZiBpbnRlZ2VycyBuPHN1Yj4xPFwvc3ViPiwgLi4uLCBuPHN1Yj5rPFwvc3ViPiwgaW4gd2hpY2ggKDEpIG4gPSBuPHN1Yj4xPFwvc3ViPiwgKDIpIGsgJmdlOyAxLCAoMykgZm9yIGFsbCAxICZsZTsgaSAmbHQ7IGssIG48c3ViPmkrMTxcL3N1Yj4gaXMgb2J0YWluZWQgZnJvbSBuaSBieSBmaXJzdCBkaXNjYXJkaW5nIHRoZSBkaWdpdHMgb2YgYSBzdWJmYWN0b3Igb2YgbjxzdWI+aTxcL3N1Yj4sIGFuZCB0aGVuIGRpc2NhcmRpbmcgbGVhZGluZyB6ZXJvcywgaWYgYW55LCBhbmQgKDQpIG5rIGhhcyBubyBzdWJmYWN0b3IuIFRoZSB0ZXJtICZxdW90O3gtc3ViZmFjdG9yJnF1b3Q7IGlzIG1lYW50IHRvIHN1Z2dlc3QgdGhhdCBhIHN1YmZhY3RvciBnZXRzIHgmIzM5O2VkLCBvciBkaXNjYXJkZWQsIGFzIHlvdSBnbyBmcm9tIG9uZSBudW1iZXIgdG8gdGhlIG5leHQuIEZvciBleGFtcGxlLCAyMDA0IGhhcyB0d28gZGlzdGluY3QgeC1zdWJmYWN0b3Igc2VyaWVzLCB0aGUgc2Vjb25kIG9mIHdoaWNoIGNhbiBiZSBvYnRhaW5lZCBpbiB0d28gZGlzdGluY3Qgd2F5cy4gVGhlIGhpZ2hsaWdodGVkIGRpZ2l0cyBzaG93IHRoZSBzdWJmYWN0b3IgdGhhdCB3YXMgcmVtb3ZlZCB0byBwcm9kdWNlIHRoZSBuZXh0IG51bWJlciBpbiB0aGUgc2VyaWVzLjxcL3A+XHJcblxyXG48cD48ZW0+PHN0cm9uZz48dT4yPFwvdT48XC9zdHJvbmc+PFwvZW0+MDA0ICZuYnNwOyA0PGJyIFwvPlxyXG4yMDA8dT48c3Ryb25nPjxlbT40PFwvZW0+PFwvc3Ryb25nPjxcL3U+ICZuYnNwOyA8dT48ZW0+PHN0cm9uZz4yMDxcL3N0cm9uZz48XC9lbT48XC91PjAgJm5ic3A7IDA8YnIgXC8+XHJcbjIwMDx1PjxzdHJvbmc+PGVtPjQ8XC9lbT48XC9zdHJvbmc+PFwvdT4gJm5ic3A7IDx1PjxlbT48c3Ryb25nPjI8XC9zdHJvbmc+PFwvZW0+PFwvdT4wMCAmbmJzcDsgMDxcL3A+XHJcblxyXG48cD5UaGUgcHJpbWFyeSB4LXN1YmZhY3RvciBzZXJpZXMgaGFzIG1heGltYWwgbGVuZ3RoICh0aGUgbGFyZ2VzdCBrIHBvc3NpYmxlLCB1c2luZyB0aGUgbm90YXRpb24gYWJvdmUpLiBJZiB0aGVyZSBhcmUgdHdvIG9yIG1vcmUgbWF4aW1hbC1sZW5ndGggc2VyaWVzLCB0aGVuIHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3Qgc2Vjb25kIG51bWJlciBpcyBwcmltYXJ5OyBpZiBhbGwgbWF4aW1hbC1sZW5ndGggc2VyaWVzIGhhdmUgdGhlIHNhbWUgZmlyc3QgYW5kIHNlY29uZCBudW1iZXJzLCB0aGVuIHRoZSBvbmUgd2l0aCB0aGUgc21hbGxlc3QgdGhpcmQgbnVtYmVyIGlzIHByaW1hcnk7IGFuZCBzbyBvbi4gRXZlcnkgcG9zaXRpdmUgaW50ZWdlciBoYXMgYSB1bmlxdWUgcHJpbWFyeSB4LXN1YmZhY3RvciBzZXJpZXMsIGFsdGhvdWdoIGl0IG1heSBiZSBwb3NzaWJsZSB0byBvYnRhaW4gaXQgaW4gbW9yZSB0aGFuIG9uZSB3YXksIGFzIGlzIHRoZSBjYXNlIHdpdGggMjAwNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBvbmUgb3IgbW9yZSBwb3NpdGl2ZSBpbnRlZ2VycywgZWFjaCBsZXNzIHRoYW4gb25lIGJpbGxpb24sIHdpdGhvdXQgbGVhZGluZyB6ZXJvZXMsIGFuZCBvbiBhIGxpbmUgYnkgaXRzZWxmLiBGb2xsb3dpbmcgaXMgYSBsaW5lIGNvbnRhaW5pbmcgb25seSAmcXVvdDswJnF1b3Q7IHRoYXQgc2lnbmFscyB0aGUgZW5kIG9mIHRoZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcG9zaXRpdmUgaW50ZWdlciwgb3V0cHV0IGl0cyBwcmltYXJ5IHgtc3ViZmFjdG9yIHNlcmllcyB1c2luZyB0aGUgZXhhY3QgZm9ybWF0IHNob3duIGluIHRoZSBleGFtcGxlcyBiZWxvdy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d