DEPOSIT - Deposit

Banks offer deposit schemes of various kinds to attract customers. In an r -year progressively reducing recurring deposit scheme (PRRDS) of a bank, a customer is required to deposit progressively reducing amounts every year for r years. Depending on the duration r of the scheme and the total amount T deposited in r years, the bank offers to return on maturity, i.e., after the expiry of r years, an amount R, which is equal to k times the amount deposited in the first year. The bank ensures that the return R looks attractive by making a suitable choice of k ; k being a natural number.

In a PRRDS, the amount to be deposited in each but the last two years is exactly equal to the sum of amounts to be deposited in the next two years. The amounts to be deposited in the last two years, say x in the last year and y in the last but one year, are progressively reducing (x, y > 0;y > x) and are determined so that the total amount deposited in r years is exactly equal to the specified amount T. Assume that all deposits are in whole number of Rupees.

Write a program for the bank, so that given r, k and T, the program computes x and y for which the return R is maximum. For example in a 4-year scheme with r = 4, k = 3 and T = 500, the progressively reducing recurring deposits 248, 126, 122 and 4, ensures the maximum return R = 744 with x = 4 and y = 122.

Input

The input may contain multiple test cases.

For each test case there is only one input line. The line gives values of r, k and T. Assume that r is not greater than 20.

A line containing a zero '0' as the first character follows the last case.

Output

For each test case there is only one output line. The line gives the computed values of x, y and R.

Example

Input
4 3 500
5 3 10000
6 4 8000
8 5 12000
0

Output
4 122 744
5 1425 12855
1 666 13332
1 363 23635

Added by:Jimmy
Date:2008-12-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2007

hide comments
2010-05-04 06:41:23 Seshadri R
@Ravi Kiran: r will be at least two since the output has to contain values of x and y. So, the case that r=1 will never arise
2009-12-10 19:20:39 Ravi Kiran
Do we hav to handle the case when r=1??
2009-07-07 14:25:54 Vijay
what is the maximum value of T?
2009-07-04 08:21:22 numerix
madhav is right, but there seems to be large i/o: you have to do a lot of optimization to get it AC within the time limit using python.
2009-02-17 10:09:11 madhav
The problem is purely mathematical and very easy also
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.