시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 203 59 52 30.058%

문제

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

창영이가 만들 냉장고는 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+XHJcblx0blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHViMGM5XHVjN2E1XHVhY2UwKFx1Y2QxZCBcdWJhNzRcdWM4MDFcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWIwYzlcdWM3YTVcdWFjZTApXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIGEgYiBjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Y2QxZCBcdWJhNzRcdWM4MDFcdWM3NzQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWIwYzlcdWM3YTVcdWFjZTBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjAsIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzU5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlZXIgUmVmcmlnZXJhdG9yIiwiZGVzY3JpcHRpb24iOiI8cD5CZWVyIExvdmVycyBDbHViIG1ha2VzIHJlZ3VsYXIgcGFydGllcy4gVGhleSBoYXRlIHdhcm0gYmVlciwgYnV0IGNsdWImcnNxdW87cyByZWZyaWdlcmF0b3IgaXMgdG9vIHNtYWxsIHRvIHN0b3JlIGVub3VnaCBiZWVyIGZvciB0aGUgd2hvbGUgY29tcGFueS4gU28gdGhleSBkZWNpZGVkIHRvIG9yZGVyIGEgc3BlY2lhbCBzdXBlci1iaWcgYmVlciByZWZyaWdlcmF0b3IuIFRoZSBuZXcgcmVmcmlnZXJhdG9yIHNob3VsZCBiZSBhIHBhcmFsbGVsZXBpcGVkIGEgJnRpbWVzOyBiICZ0aW1lczsgYyBhbmQgc3RvcmUgZXhhY3RseSBuIGN1YmljYWwgMSAmdGltZXM7IDEgJnRpbWVzOyAxIGJlZXIgYm94ZXMgKHRoZSBjbHViIGhhcyBuIG1lbWJlcnMpLiBUbyBkZWNyZWFzZSBsb3NzZXMgb2YgY29sZCwgdGhlIHRvdGFsIGFyZWEgb2YgdGhlIHN1cmZhY2Ugb2YgdGhlIHJlZnJpZ2VyYXRvciBtdXN0IGJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIGNhcGFjaXR5IG9mIHRoZSByZWZyaWdlcmF0b3IgbXVzdCBiZSAxMiwgdGhlIHBvc3NpYmxlIHZhcmlhbnRzIGFyZTo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjIwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MTAlXCI+RGltZW5zaW9uczxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoxMCVcIj5TdXJmYWNlIEFyZWE8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjMgJnRpbWVzOyAyICZ0aW1lczsgMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NCAmdGltZXM7IDMgJnRpbWVzOyAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4zODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42ICZ0aW1lczsgMiAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjQwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEyICZ0aW1lczsgMSAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjUwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG5cclxuPHA+VGhlIGJlc3QgdmFyaWFudCBpbiB0aGlzIGNhc2UgaXMgMyAmdGltZXM7IDIgJnRpbWVzOyAyLjxcL3A+XHJcblxyXG48cD5IZWxwIHRoZSBiZWVyIGxvdmVycyB0byBcdWZiMDFuZCB0aGUgb3B0aW1hbCBkaW1lbnNpb25zIGZvciB0aGVpciBuZXcgcmVmcmlnZXJhdG9yLjxcL3A+IiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjY8XC9zdXA+KSAmbWRhc2g7IHRoZSBjYXBhY2l0eSBvZiB0aGUgcmVmcmlnZXJhdG9yLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aHJlZSBpbnRlZ2VyIG51bWJlcnM6IGEsIGIgYW5kIGMgJm1kYXNoOyB0aGUgb3B0aW1hbCBkaW1lbnNpb25zIG9mIHRoZSByZWZyaWdlcmF0b3IuIElmIHRoZXJlIGFyZSBzZXZlcmFsIHNvbHV0aW9ucywgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==