Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2288
Across the River

Time Limit: 10 Seconds      Memory Limit: 32768 KB

n men and m women (1 <= n <= m <= 200) want to cross a river. There is only one boat on the river, and it can carry k (k >= 1) people at most at a time. So they have to design a strategy to cross the river, but the following rule must be obeyed. That is, at any time, either on the riverside or on the boat, there's no woman or the number of women is no less than the number of men. So you task is to design a strategy that take all the people across the river, and this strategy takes the least steps. (take some people from one side to the other side counts one step). If no such strategy exists, just output "Impossible".


The input consists of several test cases, each input consists of three integers n, m, k. The input is terminated by EOF.


For each test case, output the least steps if possible, or "Impossible" if there is no such strategy.

Sample Input

2 2 2
2 2 1

Sample Output


Author: DAI, Wenbin
Source: ZOJ Monthly, January 2005
Submit    Status