시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 197 53 49 28.824%

문제

맥주를 좋아하는 창영이는 냉장고에 맥주를 보관한다. 일반 냉장고에 음식과 맥주를 함께 보관하다보니 창영이의 냉장고에는 맥주를 넣을 곳이 점점 없어지고 있었다. 창영이는 맥주 전용 냉장고를 만들기로 결심했다.

창영이가 만들 냉장고는 a × b × c 크기의 직육면체이고, n개의 맥주 박스를 보관할 수 있다. 맥주 박스는 크기가 1 × 1 × 1인 정육면체이다. 창영이는 맥주를 신선하게 보관하기 위해서, 냉장고의 총 면적을 가능한 작게 만드려고 한다.

예를 들어, 냉장고의 용량이 12라면, 다음과 같은 네가지 냉장고를 만들 수 있다.

크기 총 면적
3 × 2 × 2 32
4 × 3 × 1 38
6 × 2 × 1 40
12 × 1 × 1 50

이 경우에 가장 좋은 냉장고는 3 × 2 × 2이다.

n이 주어졌을 때, 창영이가 만들 가장 좋은 냉장고(총 면적이 가장 작은 냉장고)의 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 106)

출력

첫째 줄에 a b c를 출력한다. 만약 총 면적이 가장 작은 냉장고가 여러가지인 경우, 아무거나 출력한다.

예제 입력 1

12

예제 출력 1

3 2 2

힌트

W3sicHJvYmxlbV9pZCI6IjM1OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZTVcdWM4ZmMgXHViMGM5XHVjN2E1XHVhY2UwIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHViOWU1XHVjOGZjXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViMGM5XHVjN2E1XHVhY2UwXHVjNWQwIFx1YjllNVx1YzhmY1x1Yjk3YyBcdWJjZjRcdWFkMDBcdWQ1NWNcdWIyZTQuIFx1Yzc3Y1x1YmMxOCBcdWIwYzlcdWM3YTVcdWFjZTBcdWM1ZDAgXHVjNzRjXHVjMmRkXHVhY2ZjIFx1YjllNVx1YzhmY1x1Yjk3YyBcdWQ1NjhcdWFlZDggXHViY2Y0XHVhZDAwXHVkNTU4XHViMmU0XHViY2Y0XHViMmM4IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWIwYzlcdWM3YTVcdWFjZTBcdWM1ZDBcdWIyOTQgXHViOWU1XHVjOGZjXHViOTdjIFx1YjEyM1x1Yzc0NCBcdWFjZjNcdWM3NzQgXHVjODEwXHVjODEwIFx1YzVjNlx1YzViNFx1YzljMFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTVcdWM4ZmMgXHVjODA0XHVjNmE5IFx1YjBjOVx1YzdhNVx1YWNlMFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzBcdWI4NWMgXHVhY2IwXHVjMmVjXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YjBjOVx1YzdhNVx1YWNlMFx1YjI5NCBhICZ0aW1lczsgYiAmdGltZXM7IGMgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzljMVx1YzcyMVx1YmE3NFx1Y2NiNFx1Yzc3NFx1YWNlMCwgblx1YWMxY1x1Yzc1OCBcdWI5ZTVcdWM4ZmMgXHViYzE1XHVjMmE0XHViOTdjIFx1YmNmNFx1YWQwMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWI5ZTVcdWM4ZmMgXHViYzE1XHVjMmE0XHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCAxICZ0aW1lczsgMSAmdGltZXM7IDFcdWM3NzggXHVjODE1XHVjNzIxXHViYTc0XHVjY2I0XHVjNzc0XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWU1XHVjOGZjXHViOTdjIFx1YzJlMFx1YzEyMFx1ZDU1OFx1YWM4YyBcdWJjZjRcdWFkMDBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWIwYzlcdWM3YTVcdWFjZTBcdWM3NTggXHVjZDFkIFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkxXHVhYzhjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjBjOVx1YzdhNVx1YWNlMFx1Yzc1OCBcdWM2YTlcdWI3YzlcdWM3NzQgMTJcdWI3N2NcdWJhNzQsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViMTI0XHVhYzAwXHVjOWMwIFx1YjBjOVx1YzdhNVx1YWNlMFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjIwJTtcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJTtcIj5cclxuXHRcdFx0XHRcdWQwNmNcdWFlMzA8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MTAlO1wiPlxyXG5cdFx0XHRcdFx1Y2QxZCBcdWJhNzRcdWM4MDE8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDMgJnRpbWVzOyAyICZ0aW1lczsgMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MzI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NCAmdGltZXM7IDMgJnRpbWVzOyAxPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQzODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ2ICZ0aW1lczsgMiAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDQwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDEyICZ0aW1lczsgMSAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDUwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHViMGM5XHVjN2E1XHVhY2UwXHViMjk0IDMgJnRpbWVzOyAyICZ0aW1lczsgMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHViMGM5XHVjN2E1XHVhY2UwKFx1Y2QxZCBcdWJhNzRcdWM4MDFcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWIwYzlcdWM3YTVcdWFjZTApXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIGEgYiBjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Y2QxZCBcdWJhNzRcdWM4MDFcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWIwYzlcdWM3YTVcdWFjZTBcdWFjMDAgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMCwgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNTk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmVlciBSZWZyaWdlcmF0b3IiLCJkZXNjcmlwdGlvbiI6IjxwPkJlZXIgTG92ZXJzIENsdWIgbWFrZXMgcmVndWxhciBwYXJ0aWVzLiBUaGV5IGhhdGUgd2FybSBiZWVyLCBidXQgY2x1YiZyc3F1bztzIHJlZnJpZ2VyYXRvciBpcyB0b28gc21hbGwgdG8gc3RvcmUgZW5vdWdoIGJlZXIgZm9yIHRoZSB3aG9sZSBjb21wYW55LiBTbyB0aGV5IGRlY2lkZWQgdG8gb3JkZXIgYSBzcGVjaWFsIHN1cGVyLWJpZyBiZWVyIHJlZnJpZ2VyYXRvci4gVGhlIG5ldyByZWZyaWdlcmF0b3Igc2hvdWxkIGJlIGEgcGFyYWxsZWxlcGlwZWQgYSAmdGltZXM7IGIgJnRpbWVzOyBjIGFuZCBzdG9yZSBleGFjdGx5IG4gY3ViaWNhbCAxICZ0aW1lczsgMSAmdGltZXM7IDEgYmVlciBib3hlcyAodGhlIGNsdWIgaGFzIG4gbWVtYmVycykuIFRvIGRlY3JlYXNlIGxvc3NlcyBvZiBjb2xkLCB0aGUgdG90YWwgYXJlYSBvZiB0aGUgc3VyZmFjZSBvZiB0aGUgcmVmcmlnZXJhdG9yIG11c3QgYmUgYXMgc21hbGwgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiB0aGUgY2FwYWNpdHkgb2YgdGhlIHJlZnJpZ2VyYXRvciBtdXN0IGJlIDEyLCB0aGUgcG9zc2libGUgdmFyaWFudHMgYXJlOjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MjAlXCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoxMCVcIj5EaW1lbnNpb25zPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJVwiPlN1cmZhY2UgQXJlYTxcL3RoPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGhlYWQ+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MyAmdGltZXM7IDIgJnRpbWVzOyAyPFwvdGQ+XHJcblx0XHRcdDx0ZD4zMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD40ICZ0aW1lczsgMyAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjM4PFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjYgJnRpbWVzOyAyICZ0aW1lczsgMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+NDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MTIgJnRpbWVzOyAxICZ0aW1lczsgMTxcL3RkPlxyXG5cdFx0XHQ8dGQ+NTA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcblxyXG48cD5UaGUgYmVzdCB2YXJpYW50IGluIHRoaXMgY2FzZSBpcyAzICZ0aW1lczsgMiAmdGltZXM7IDIuPFwvcD5cclxuXHJcbjxwPkhlbHAgdGhlIGJlZXIgbG92ZXJzIHRvIFx1ZmIwMW5kIHRoZSBvcHRpbWFsIGRpbWVuc2lvbnMgZm9yIHRoZWlyIG5ldyByZWZyaWdlcmF0b3IuPFwvcD4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyBzaW5nbGUgaW50ZWdlciBudW1iZXIgbiAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+NjxcL3N1cD4pICZtZGFzaDsgdGhlIGNhcGFjaXR5IG9mIHRoZSByZWZyaWdlcmF0b3IuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRocmVlIGludGVnZXIgbnVtYmVyczogYSwgYiBhbmQgYyAmbWRhc2g7IHRoZSBvcHRpbWFsIGRpbWVuc2lvbnMgb2YgdGhlIHJlZnJpZ2VyYXRvci4gSWYgdGhlcmUgYXJlIHNldmVyYWwgc29sdXRpb25zLCBvdXRwdXQgYW55IG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d