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^{15} 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!`”.

Public test cases

**Input**

4 5 2 1296 4 5 2 1297 4 5 2 1000000 1 5 3 60 1 5 3 61 1 6 1 5 1 6 1 1 1 6 10 1 5 6 5 123456789012

**Output**

2 1 Impossible, Takeshi! 0 Impossible, Takeshi! 1 5 Impossible, Takeshi! 0

Information

- Author
- Marçal Garolera
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++