У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:
- Наполнить сосуд A (обозначается
>A).
- Наполнить сосуд B (обозначается
>B).
- Вылить воду из сосуда A (обозначается
A>).
- Вылить воду из сосуда B (обозначается
B>).
- Перелить воду из сосуда A в сосуд B (обозначается как
A>B).
- Перелить воду из сосуда B в сосуд A (обозначается как
B>A).
Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полностью наполняется.
Входные данные: Программа получает на вход три натуральных числа A, B, N, не превосходящих 10
4.
Выходные данные: Необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст
Impossible.
Количество операций в алгоритме не должно превышать 105. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 105 операций.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
5
1 |
>A
A>B
>A
A>B
|
| 2 |
3
5
6 |
Impossible
|