시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB114846639843.593%

문제

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

창영이가 만들 냉장고는 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

예제 입력 2

13

예제 출력 2

1 13 1

예제 입력 3

1000000

예제 출력 3

100 100 100
W3sicHJvYmxlbV9pZCI6IjM1OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZTVcdWM4ZmMgXHViMGM5XHVjN2E1XHVhY2UwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI5ZTVcdWM4ZmNcdWI5N2MgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIwYzlcdWM3YTVcdWFjZTBcdWM1ZDAgXHViOWU1XHVjOGZjXHViOTdjIFx1YmNmNFx1YWQwMFx1ZDU1Y1x1YjJlNC4gXHVjNzdjXHViYzE4IFx1YjBjOVx1YzdhNVx1YWNlMFx1YzVkMCBcdWM3NGNcdWMyZGRcdWFjZmMgXHViOWU1XHVjOGZjXHViOTdjIFx1ZDU2OFx1YWVkOCBcdWJjZjRcdWFkMDBcdWQ1NThcdWIyZTRcdWJjZjRcdWIyYzggXHVjYzNkXHVjNjAxXHVjNzc0XHVjNzU4IFx1YjBjOVx1YzdhNVx1YWNlMFx1YzVkMFx1YjI5NCBcdWI5ZTVcdWM4ZmNcdWI5N2MgXHViMTIzXHVjNzQ0IFx1YWNmM1x1Yzc3NCBcdWM4MTBcdWM4MTAgXHVjNWM2XHVjNWI0XHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YjllNVx1YzhmYyBcdWM4MDRcdWM2YTkgXHViMGM5XHVjN2E1XHVhY2UwXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMFx1Yjg1YyBcdWFjYjBcdWMyZWNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTQgXHViMGM5XHVjN2E1XHVhY2UwXHViMjk0IGEgJnRpbWVzOyBiICZ0aW1lczsgYyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjOWMxXHVjNzIxXHViYTc0XHVjY2I0XHVjNzc0XHVhY2UwLCBuXHVhYzFjXHVjNzU4IFx1YjllNVx1YzhmYyBcdWJjMTVcdWMyYTRcdWI5N2MgXHViY2Y0XHVhZDAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjllNVx1YzhmYyBcdWJjMTVcdWMyYTRcdWIyOTQgXHVkMDZjXHVhZTMwXHVhYzAwIDEgJnRpbWVzOyAxICZ0aW1lczsgMVx1Yzc3OCBcdWM4MTVcdWM3MjFcdWJhNzRcdWNjYjRcdWM3NzRcdWIyZTQuIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTVcdWM4ZmNcdWI5N2MgXHVjMmUwXHVjMTIwXHVkNTU4XHVhYzhjIFx1YmNmNFx1YWQwMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMsIFx1YjBjOVx1YzdhNVx1YWNlMFx1Yzc1OCBcdWFjODlcdWIxMTNcdWM3NzRcdWI5N2MgXHVhYzAwXHViMmE1XHVkNTVjIFx1Yzc5MVx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIwYzlcdWM3YTVcdWFjZTBcdWM3NTggXHVjNmE5XHViN2M5XHVjNzc0IDEyXHViNzdjXHViYTc0LCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjEyNFx1YWMwMFx1YzljMCBcdWIwYzlcdWM3YTVcdWFjZTBcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoyMCU7XCI+XHJcblx0PHRoZWFkPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoxMCU7XCI+XHVkMDZjXHVhZTMwPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJTtcIj5cdWFjODlcdWIxMTNcdWM3NzQ8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjMgJnRpbWVzOyAyICZ0aW1lczsgMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NCAmdGltZXM7IDMgJnRpbWVzOyAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4zODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42ICZ0aW1lczsgMiAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjQwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEyICZ0aW1lczsgMSAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjUwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG48cD5cdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHViMGM5XHVjN2E1XHVhY2UwXHViMjk0IDMgJnRpbWVzOyAyICZ0aW1lczsgMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0IFx1YWMwMFx1YzdhNSBcdWM4OGJcdWM3NDAgXHViMGM5XHVjN2E1XHVhY2UwKFx1YWM4OVx1YjExM1x1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YjBjOVx1YzdhNVx1YWNlMClcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjY8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgYSBiIGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzg5XHViMTEzXHVjNzc0XHVhYzAwJm5ic3A7XHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWIwYzlcdWM3YTVcdWFjZTBcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjAsIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzU5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJlZXIgUmVmcmlnZXJhdG9yIiwiZGVzY3JpcHRpb24iOiI8cD5CZWVyIExvdmVycyBDbHViIG1ha2VzIHJlZ3VsYXIgcGFydGllcy4gVGhleSBoYXRlIHdhcm0gYmVlciwgYnV0IGNsdWImcnNxdW87cyByZWZyaWdlcmF0b3IgaXMgdG9vIHNtYWxsIHRvIHN0b3JlIGVub3VnaCBiZWVyIGZvciB0aGUgd2hvbGUgY29tcGFueS4gU28gdGhleSBkZWNpZGVkIHRvIG9yZGVyIGEgc3BlY2lhbCBzdXBlci1iaWcgYmVlciByZWZyaWdlcmF0b3IuIFRoZSBuZXcgcmVmcmlnZXJhdG9yIHNob3VsZCBiZSBhIHBhcmFsbGVsZXBpcGVkIGEgJnRpbWVzOyBiICZ0aW1lczsgYyBhbmQgc3RvcmUgZXhhY3RseSBuIGN1YmljYWwgMSAmdGltZXM7IDEgJnRpbWVzOyAxIGJlZXIgYm94ZXMgKHRoZSBjbHViIGhhcyBuIG1lbWJlcnMpLiBUbyBkZWNyZWFzZSBsb3NzZXMgb2YgY29sZCwgdGhlIHRvdGFsIGFyZWEgb2YgdGhlIHN1cmZhY2Ugb2YgdGhlIHJlZnJpZ2VyYXRvciBtdXN0IGJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaWYgdGhlIGNhcGFjaXR5IG9mIHRoZSByZWZyaWdlcmF0b3IgbXVzdCBiZSAxMiwgdGhlIHBvc3NpYmxlIHZhcmlhbnRzIGFyZTo8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjIwJVwiPlxyXG5cdDx0aGVhZD5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MTAlXCI+RGltZW5zaW9uczxcL3RoPlxyXG5cdFx0XHQ8dGggc3R5bGU9XCJ3aWR0aDoxMCVcIj5TdXJmYWNlIEFyZWE8XC90aD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3RoZWFkPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjMgJnRpbWVzOyAyICZ0aW1lczsgMjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NCAmdGltZXM7IDMgJnRpbWVzOyAxPFwvdGQ+XHJcblx0XHRcdDx0ZD4zODxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD42ICZ0aW1lczsgMiAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjQwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjEyICZ0aW1lczsgMSAmdGltZXM7IDE8XC90ZD5cclxuXHRcdFx0PHRkPjUwPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG5cclxuPHA+VGhlIGJlc3QgdmFyaWFudCBpbiB0aGlzIGNhc2UgaXMgMyAmdGltZXM7IDIgJnRpbWVzOyAyLjxcL3A+XHJcblxyXG48cD5IZWxwIHRoZSBiZWVyIGxvdmVycyB0byBcdWZiMDFuZCB0aGUgb3B0aW1hbCBkaW1lbnNpb25zIGZvciB0aGVpciBuZXcgcmVmcmlnZXJhdG9yLjxcL3A+IiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgc2luZ2xlIGludGVnZXIgbnVtYmVyIG4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjY8XC9zdXA+KSAmbWRhc2g7IHRoZSBjYXBhY2l0eSBvZiB0aGUgcmVmcmlnZXJhdG9yLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aHJlZSBpbnRlZ2VyIG51bWJlcnM6IGEsIGIgYW5kIGMgJm1kYXNoOyB0aGUgb3B0aW1hbCBkaW1lbnNpb25zIG9mIHRoZSByZWZyaWdlcmF0b3IuIElmIHRoZXJlIGFyZSBzZXZlcmFsIHNvbHV0aW9ucywgb3V0cHV0IGFueSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=