Задача F. Планета Плюк

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:pluk.in   Ограничение памяти:64 Мб
Выходной файл:pluk.out  

Условие

На планете Плюк, поверхность которой мы будем считать абсолютно плоской, был разработан новый принцип перемещения единственного имеющегося там транспортного средства — пепелаца. А именно, на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку ( − 1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3,  − 3).

Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу. Житель проживает около точки с координатами (x1, y1), а его друг — около точки с координатами (x2, y2). Помогите жителю с помощью станций управления пепелацем оказаться как можно ближе к месту, где проживает его друг, чтобы потом меньше было идти по пустыне.

Поскольку перемещения мгновенные и абсолютно бесплатные, то минимизировать количество перемещений не надо.

Формат входного файла

Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по абсолютной величине.

Формат выходного файла

Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).

Поворот по часовой стрелке относительно станции A обозначается как "+A", поворот против часовой стрелки относительно станции A обозначается как "-A", соответствующие повороты относительно станции B обозначаются как "+B" и "-B". Выводите по одному перемещению на строке.

Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.

Примеры тестов

Входной файл (pluk.in) Выходной файл (pluk.out)
1
3 1
3 -3
-A
+B
+B
2
0 0
3 0
-B
-B

0.411s 0.165s 17