eolymp
Competitions

Full Search

Grocery store

A cashier in a grocery store seems to have difficulty in distinguishing the multiplication symbol and the addition symbol. To make things easier for him, you want to buy goods in such a way that the product of their prices is the same as the sum of their prices.

Of course, if you buy only one item, this is always true. With two items and three items, it still seems quite a boring task to you, so now you are interested in finding possible prices of four items such that the sum of the four prices is equal to the product of the four prices. You should consider the prices are in with two digits after the decimal point. Obviously, each product costs at least one cent.

Input

Contains one real number with two digits after the decimal point - the sum S (5S25).

Output

Print all solutions which have a sum of the four items of at most S€. For each solution, print one line with the prices of the four items in non-decreasing order, with one space character between them. The solutions should be printed by increasing cost of the first product. If for several solutions the cost of the first product is the same, then you should print them by increasing cost of the second product. In the event that the values of the first and second products are equal, print by increasing value of the third product. Each solution should be printed only once.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6.7
Output example #1
1.00 1.75 1.90 2.00
1.10 1.50 2.00 2.00
1.25 1.25 1.92 2.21
1.25 1.40 1.86 2.00
1.25 1.60 1.75 1.84
Source 2007 University of Ulm Local Contest, July 6