This page is still under construction.

Parts of this page are still being built. What you see may change.

Three Sons

Time limit1sMemory limit512 MB

Summary
Split an integer n into three strictly increasing positive parts a < b < c whose squares sum to the minimum possible value.
Level

Medium5 of 10

Topics
Math, Greedy, Implementation
Solved
No attempts yet

Problem

In the domain of the king of Flatlandia there is a straight road nn kilometers long, and a huge forest lies on one side of it. The king of Flatlandia took up the ideas of nature conservation and decided to turn his forest into a nature reserve. But his sons objected: they wanted to receive these lands as an inheritance.

The king has three sons: the youngest, the middle, and the eldest. The king decided that the parts of the forest he leaves to his sons as an inheritance will not be included in the reserve. When drawing up the will, the king wants the following conditions to hold for the plots:

  • Each plot must be a square whose side length is expressed by a positive integer. One side of each square must lie on the road. Let the plots have sizes a×aa \times a, b×bb \times b, and c×cc \times c.
  • The sides of the squares must completely cover the road: the value of a+b+ca + b + c must equal nn.
  • The youngest son's plot must be strictly smaller than the middle son's plot, and the middle son's plot must in turn be strictly smaller than the eldest son's plot, that is, the inequality a<b<ca < b < c must hold.
  • The total area of the plots a2+b2+c2a^2 + b^2 + c^2 must be minimal.

You must write a program that, given the length of the road, determines the sizes of the plots to be allotted to the king's sons.

Input

The input file contains a single integer nn (6≤n≤1096 \le n \le 10^9).

Output

The output file must contain three positive integers separated by spaces: aa, bb, and cc, the side lengths of the plots to be allotted to the youngest, middle, and eldest son, respectively. If there are several optimal solutions, you may output any of them.

Hint

Examples1

  1. Example 1

    Input
    6
    
    Expected output
    1 2 3