В улье, изображенном на рисунке, в поисках нужной соты ползает пчела. Как видно из рисунка, соты представляют собой шестиугольники, и пчела может переползать из одной соты в соседнюю с ней вдоль заданных осей координат X, Y или Z. После того, как пчела оказалась в нужной ей соте, она должна возвратиться в исходную соту по пути, содержащем по возможности наименьшее количество промежуточных сот.
Путь пчелы задается в виде последовательности пар следующего вида: сначала записывается буква (X, Y или Z), определяющая направление движения, а затем целое число, задающее, на сколько сот пчела перемещается в этом направлении. Требуется написать программу, которая вычисляет кратчайший обратный путь.
В первой строке входного файла INPUT.TXT содержится целое число N (N<32000) - количество звеньев пути пчелы из начальной соты в конечную. Последующие N строк содержат описания звеньев пути пчелы из начальной соты в конечную в порядке движения. В каждой строке сначала идет буква (X, Y или Z), определяющая направление движения, а затем - целое число К, задающее, на сколько сот пчела перемешается в этом направлении. Буква и число разделяются ровно одним пробелом.
Выходной файл OUTPUT.TXT должен содержать описание искомого пути пчелы в том же формате, что и во входном файле.
| Пример INPUT.TXT: | OUTPUT.TXT для примера: |
| 4 Z -2 Y 3 Z 3 X -1 | 2 Y -2 Z -2 |