У исполнителя “Водолей” есть два сосуда, первый объемом 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
|