В тридевятом царстве, в тридесятом государстве... Итак, начнем с того момента, как Иванушка-дурачок встретил Змея Горыныча. Достал Иванушка меч-кладенец, и началась у них битва. Сначала у Змея Горыныча было h голов и t хвостов. Каждым ударом меча Иванушка может отрубить либо несколько голов (от 1 до n, но не больше, чем голов у Горыныча в данный момент), либо несколько хвостов (от 1 до m, но не больше, чем хвостов у Горыныча в данный момент). При этом (о, ужас!) у Змея Горыныча могут вырастать новые головы и хвосты. Причем количество вырастающих голов и хвостов однозначно определяется в зависимости от количества голов или хвостов, отрубленных очередным ударом. Когда суммарное количество голов и хвостов станет строго больше R, Змей Горыныч нанесет свой решающий удар и повергнет Иванушку-дурачка. Поэтому Иванушка стремится как можно быстрее отрубить все головы и хвосты Змею и победить. Возможен и третий вариант развития событий: ни один из противников не сможет одолеть другого и они будут сражаться бесконечно.

Скоро сказка сказывается, да нескоро дело делается. Ваша задача — написать программу, определяющую исход битвы. Учтите, что Иванушка-дурачок наносит удары последовательно. После каждого удара у Горыныча вырастают новые головы и хвосты в зависимости от количества отрубленных. Змей Горыныч считается побежденным, если после очередного удара он лишается всех голов и хвостов и у него не вырастает новых. Иванушка сражается оптимально (дурачкам везет!), т.е.

• если Иванушка может победить, он побеждает за наименьшее количество ударов;
• если победить Горыныча невозможно, но можно бесконечно долго сопротивляться ему, то Иванушка выбирает именно эту стратегию;
• если победу в любом случае одержит Змей Горыныч, Иванушка стремится сопротивляться ему как можно дольше.