시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB186535.714%

문제

한 수열의 부분수열은 주어진 수열에서 몇 개의(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

예제 입력 2

7457762

예제 출력 2

7457762 5772 77 7
W3sicHJvYmxlbV9pZCI6IjIzNjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCgxXHVhYzFjIFx1Yzc3NFx1YzBjMSkgXHVjMjJiXHVjNzkwXHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YzVlYyBcdWM1YmJcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjIFx1YzgxY1x1YWM3MFx1ZDU1OFx1YjI5NCBcdWMyMThcdWI0ZTRcdWM3NzQgXHVhZjJkIFx1YzVmMFx1YzE4ZFx1YzgwMVx1Yzc3YyBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDEyMzRcdWM3NTggXHViZDgwXHViZDg0XHVjMjE4XHVjNWY0XHViODVjXHViMjk0IDEsIDIsIDEyLCAxMywgMjQgXHViNGYxXHVjNzc0IFx1Yzc4OFx1YzljMFx1YjljYywgMTIzNFx1YjI5NCBcdWM4MWNcdWFjNzBcdWQ1NWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YyBcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1N2RcdWMyMThcdWJkODBcdWJkODRcdWMyMThcdWM1ZjRcdWM3NzRcdWI3ODAsIFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM1N2RcdWMyMThcdWM3NzggXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCA4MDEzODI0XHVjNzU4IFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yjg1Y1x1YjI5NCA4LCAxMywgMTQgXHViNGYxXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1ZDU1YyBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBOXHVjNWQwXHVjMTFjIFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjODFjXHVhYzcwXHVkNTc0IFx1YjJlNFx1Yzc0YyBcdWMyMTggTlsyXVx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1Yzc3NCBOWzJdXHVjNWQwXHVjMTFjIFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI2MTAgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBOWzNdXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVhY2UwLCBOWzNdXHVjNWQwXHVjMTFjIFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI2MTAgXHVkNTU4XHViMDk4IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBOWzRdXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YjJlNFx1Yzc0YyBcdWMyMThcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWM3NDQgXHViNTRjXHVhZTRjXHVjOWMwIFx1YmMxOFx1YmNmNVx1ZDU1OFx1YmE3NCBOLCBOWzJdLCAmaGVsbGlwOywgTltrXVx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMga1x1Yjk3YyBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+ODAxMzgyNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU3ZFx1YzIxOFx1YmQ4MFx1YmQ4NFx1YzIxOFx1YzVmNCA4MFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NThcdWM1ZWMgTlsyXT0xMzgyNFx1Yzc0NCBcdWM1YmJcdWFjZTAsIE5bM109MTMyNCwmbmJzcDsgTls0XT0xMzIsIE5bNV09MTIsIE5bNl09MVx1Yzc0NCBcdWM1YmJcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YyBrPTZcdWM3NzQgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVhY2JkXHVjNmIwXHVhYzAwIGtcdWFjMDAgXHVjODFjXHVjNzdjIFx1Y2VlNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzI4XHViODQwXHViODVjIE4sIE5bMV0sIE5bMl0sICZoZWxsaXA7LCBOW2tdXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMzYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJpbWFyeSBYLVN1YmZhY3RvciBTZXJpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCBuIGJlIGFueSBwb3NpdGl2ZSBpbnRlZ2VyLiBBIGZhY3RvciBvZiBuIGlzIGFueSBudW1iZXIgdGhhdCBkaXZpZGVzIGV2ZW5seSBpbnRvIG4sIHdpdGhvdXQgbGVhdmluZyBhIHJlbWFpbmRlci4gRm9yIGV4YW1wbGUsIDEzIGlzIGEgZmFjdG9yIG9mIDUyLCBzaW5jZSA1MlwvMTMgPSA0LiBBIHN1YnNlcXVlbmNlIG9mIG4gaXMgYSBudW1iZXIgd2l0aG91dCBhIGxlYWRpbmcgemVybyB0aGF0IGNhbiBiZSBvYnRhaW5lZCBmcm9tIG4gYnkgZGlzY2FyZGluZyBvbmUgb3IgbW9yZSBvZiBpdHMgZGlnaXRzLiBGb3IgZXhhbXBsZSwgMiwgMTMsIDgwMSwgODgyLCBhbmQgMTMyNCBhcmUgc3Vic2VxdWVuY2VzIG9mIDgwMTM4MjQsIGJ1dCAyMTQgaXMgbm90ICh5b3UgY2FuJiMzOTt0IHJlYXJyYW5nZSBkaWdpdHMpLCA4MzM0IGlzIG5vdCAoeW91IGNhbiYjMzk7dCBoYXZlIG1vcmUgb2NjdXJyZW5jZXMgb2YgYSBkaWdpdCB0aGFuIGFwcGVhciBpbiB0aGUgb3JpZ2luYWwgbnVtYmVyKSwgODAxMzgyNCBpcyBub3QgKHlvdSBtdXN0IGRpc2NhcmQgYXQgbGVhc3Qgb25lIGRpZ2l0KSwgYW5kIDAxIGlzIG5vdCAoeW91IGNhbiYjMzk7dCBoYXZlIGEgbGVhZGluZyB6ZXJvKS4gQSBzdWJmYWN0b3Igb2YgbiBpcyBhbiBpbnRlZ2VyIGdyZWF0ZXIgdGhhbiAxIHRoYXQgaXMgYm90aCBhIGZhY3RvciBhbmQgYSBzdWJzZXF1ZW5jZSBvZiBuLiA4MDEzODI0IGhhcyBzdWJmYWN0b3JzIDgsIDEzLCBhbmQgMTQuIFNvbWUgbnVtYmVycyBkbyBub3QgaGF2ZSBhIHN1YmZhY3RvcjsgZm9yIGV4YW1wbGUsIDYzNDEgaXMgbm90IGRpdmlzaWJsZSBieSA2LCAzLCA0LCA2MywgNjQsIDYxLCAzNCwgMzEsIDQxLCA2MzQsIDYzMSwgNjQxLCBvciAzNDEuPFwvcD5cclxuXHJcbjxwPkFuIHgtc3ViZmFjdG9yIHNlcmllcyBvZiBuIGlzIGEgZGVjcmVhc2luZyBzZXJpZXMgb2YgaW50ZWdlcnMgbjxzdWI+MTxcL3N1Yj4sIC4uLiwgbjxzdWI+azxcL3N1Yj4sIGluIHdoaWNoICgxKSBuID0gbjxzdWI+MTxcL3N1Yj4sICgyKSBrICZnZTsgMSwgKDMpIGZvciBhbGwgMSAmbGU7IGkgJmx0OyBrLCBuPHN1Yj5pKzE8XC9zdWI+IGlzIG9idGFpbmVkIGZyb20gbmkgYnkgZmlyc3QgZGlzY2FyZGluZyB0aGUgZGlnaXRzIG9mIGEgc3ViZmFjdG9yIG9mIG48c3ViPmk8XC9zdWI+LCBhbmQgdGhlbiBkaXNjYXJkaW5nIGxlYWRpbmcgemVyb3MsIGlmIGFueSwgYW5kICg0KSBuayBoYXMgbm8gc3ViZmFjdG9yLiBUaGUgdGVybSAmcXVvdDt4LXN1YmZhY3RvciZxdW90OyBpcyBtZWFudCB0byBzdWdnZXN0IHRoYXQgYSBzdWJmYWN0b3IgZ2V0cyB4JiMzOTtlZCwgb3IgZGlzY2FyZGVkLCBhcyB5b3UgZ28gZnJvbSBvbmUgbnVtYmVyIHRvIHRoZSBuZXh0LiBGb3IgZXhhbXBsZSwgMjAwNCBoYXMgdHdvIGRpc3RpbmN0IHgtc3ViZmFjdG9yIHNlcmllcywgdGhlIHNlY29uZCBvZiB3aGljaCBjYW4gYmUgb2J0YWluZWQgaW4gdHdvIGRpc3RpbmN0IHdheXMuIFRoZSBoaWdobGlnaHRlZCBkaWdpdHMgc2hvdyB0aGUgc3ViZmFjdG9yIHRoYXQgd2FzIHJlbW92ZWQgdG8gcHJvZHVjZSB0aGUgbmV4dCBudW1iZXIgaW4gdGhlIHNlcmllcy48XC9wPlxyXG5cclxuPHA+PGVtPjxzdHJvbmc+PHU+MjxcL3U+PFwvc3Ryb25nPjxcL2VtPjAwNCAmbmJzcDsgNDxiciBcLz5cclxuMjAwPHU+PHN0cm9uZz48ZW0+NDxcL2VtPjxcL3N0cm9uZz48XC91PiAmbmJzcDsgPHU+PGVtPjxzdHJvbmc+MjA8XC9zdHJvbmc+PFwvZW0+PFwvdT4wICZuYnNwOyAwPGJyIFwvPlxyXG4yMDA8dT48c3Ryb25nPjxlbT40PFwvZW0+PFwvc3Ryb25nPjxcL3U+ICZuYnNwOyA8dT48ZW0+PHN0cm9uZz4yPFwvc3Ryb25nPjxcL2VtPjxcL3U+MDAgJm5ic3A7IDA8XC9wPlxyXG5cclxuPHA+VGhlIHByaW1hcnkgeC1zdWJmYWN0b3Igc2VyaWVzIGhhcyBtYXhpbWFsIGxlbmd0aCAodGhlIGxhcmdlc3QgayBwb3NzaWJsZSwgdXNpbmcgdGhlIG5vdGF0aW9uIGFib3ZlKS4gSWYgdGhlcmUgYXJlIHR3byBvciBtb3JlIG1heGltYWwtbGVuZ3RoIHNlcmllcywgdGhlbiB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXN0IHNlY29uZCBudW1iZXIgaXMgcHJpbWFyeTsgaWYgYWxsIG1heGltYWwtbGVuZ3RoIHNlcmllcyBoYXZlIHRoZSBzYW1lIGZpcnN0IGFuZCBzZWNvbmQgbnVtYmVycywgdGhlbiB0aGUgb25lIHdpdGggdGhlIHNtYWxsZXN0IHRoaXJkIG51bWJlciBpcyBwcmltYXJ5OyBhbmQgc28gb24uIEV2ZXJ5IHBvc2l0aXZlIGludGVnZXIgaGFzIGEgdW5pcXVlIHByaW1hcnkgeC1zdWJmYWN0b3Igc2VyaWVzLCBhbHRob3VnaCBpdCBtYXkgYmUgcG9zc2libGUgdG8gb2J0YWluIGl0IGluIG1vcmUgdGhhbiBvbmUgd2F5LCBhcyBpcyB0aGUgY2FzZSB3aXRoIDIwMDQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygb25lIG9yIG1vcmUgcG9zaXRpdmUgaW50ZWdlcnMsIGVhY2ggbGVzcyB0aGFuIG9uZSBiaWxsaW9uLCB3aXRob3V0IGxlYWRpbmcgemVyb2VzLCBhbmQgb24gYSBsaW5lIGJ5IGl0c2VsZi4gRm9sbG93aW5nIGlzIGEgbGluZSBjb250YWluaW5nIG9ubHkgJnF1b3Q7MCZxdW90OyB0aGF0IHNpZ25hbHMgdGhlIGVuZCBvZiB0aGUgaW5wdXQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHBvc2l0aXZlIGludGVnZXIsIG91dHB1dCBpdHMgcHJpbWFyeSB4LXN1YmZhY3RvciBzZXJpZXMgdXNpbmcgdGhlIGV4YWN0IGZvcm1hdCBzaG93biBpbiB0aGUgZXhhbXBsZXMgYmVsb3cuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=