NASA's Ultrasonic Crawling Vessel, UCV for short, has arrived to galaxy UDFj - 39546284 in the Fornax constellation and has found a peculiar type of bacteria-like lifeform. As you may imagine a plan to collect samples a bring them back to earth has been set in motion. However, it would be rather unfortunate if they are all dead by the time the UCV gets back, the trip would take approximately 13.42 x 10^9 years travelling at light speed. Therefore, its necessary to pick a number of bacterium so that there are at least some of them alive when the UCV arrives back.

The UCV has studied the reproduction cycle of the bacterium inside a cryogenic pod and their behavior when released from the pod, but it lacks the algorithm to compute the final number for such a long period of time. Fortunately, it's been designed with a wormhole plugin installation mechanism that allows to upload algorithms in a matter of only a few years.

1. Aging phase: Each bacteria becomes a year older.
2. Reproduction phase: Each bacteria gives birth to a new bacteria, this is slightly different to earth bacteria in the sense that the new and old bacterium are no identical. The new bacteria is 0 years old while the old bacteria is at least 1 year old.
3. Passing phase: Each bacteria that reaches maturity, exactly M years old, dies.

Fox example, this one reproduction cycle given a 0 years old bacteria and a 1 years old bacteria if maturity is reached at 2 years old.

As you can see, during cryogenic reproduction, there's no fear of bacterium extinction, the number of births is at least as much as the number of deaths. However, when the pod is opened the bacterium enter into a strange iterative reduction phase, in each step of the reduction the oldest R bacterium die immediately; this process ends when there are fewer than R bacterium left. Note that the biggest problem arises when at some iteration there are exactly R bacterium left because they all die at that moment.

NASA ha asked you to write the algorithm that will be uploaded to the UCV to determine the number of bacterium that will exist after the pod is opened here on earth.

Input

The input contains several test cases, each one corresponding to a single simulation. Each test case starts with a line with three integers, the maturity age (1 <= M <= 50), the number of years for the UCV to come back (0 <= Y <= 10^12) and the reduction size (1 <= R <= 10^9); separated by a single space. The following line contains M integers, they
represent the number of 0, 1, ...,M - 1 years old bacterium placed inside the cryogenic pod.

The end of input is indicated by a test case with M = Y = R = 0.

Output

For each simulation output a single line containing a single integer, the number of bacterium that will be alive after the reduction process has finalized.

Example

Input:
2 1 4
1 1
2 1 2
1 1
2 2 2
1 1
2 2 5
1 1
6 0 100000
0 1 2 3 4 5
6 1000000000000 100000
0 1 2 3 4 5
0 0 0

Output:
3
1
1
0
15
21809