Knock Knock P38542

In the challenge Knock Knock w walls must be crossed to reach to the goal. The walls have d ‍doors each, all apparently identical, but some of them are made of paper and some are made of wood. For each wall, the contestant must chose a door, and run into it. If the door was made of paper, the contestant crosses it and goes to the next wall (or, if it was the last one, he has already arrived to the goal). If the door was made of wood, the contestant bounces off and he gets eliminated (and probably unconscious). As it would not be funny that the opened doors could be seen, after every contestant, the doors that he has crossed are covered with wood (so to increase the probabilities of knocking for the next contestant). At the beginning of the challenge, each wall has the same number t of wood doors.

You have been asked to prepare the challenge. The w walls with d doors each are already prepared. Knowing the number of contestants c, your problem is to decide t, the maximum number of wood doors initially in each wall, satisfying Takeshi: he wants that there are at least n different ways that the c contestants arrive to the goal.

[r]

On the right there is an instance with w = 4 walls with d = 5 doors each one, of which t = 2 (in black) are initially made of wood. The remaining d − t = 3 doors are initially made of paper. We can see one of the 1296 ways that c = 2 contestants arrive to the goal.

Input

Input consists of several cases, each one with four integer numbers: the number 1 ≤ w ≤ 5 of walls, the number 1 ≤ d ≤ 6 of doors in each wall, the number 1 ≤ c ≤ 10 of contestants, and the number 1 ≤ n ≤ 10¹⁵ of ways for the contestants to succeed.

Output

For each case, print in a line t, the maximum number of doors per wall that can be made of wood initially, while satisfying the requirement of Takeshi. If it is impossible, print “Impossible, Takeshi!”.