Задача №113690. Робот
Робот-марсоход «ТцТцПетя» двигается по поверхности Марса как ему вздумается, отправляя на Землю информацию о своих передвижениях.
«ТцТцПетя» пользуется следующей системой координат: начало координат совпадает с его начальным положением, ось \(OY\) направлена в сторону, в которую он направлен в начальный момент времени (при высадке на Марс).
Передвигается «ТцТцПетя» следующим образом: после высадки
на Марс он проезжает вперед какое-то целое число сантиметров,
от \(1\) до \(10^6;\) затем поворачивает на \(90\) градусов либо налево, либо
направо; после чего снова проезжает вперед от \(1 \ до \ 10^6\)
сантиметров;
и снова поворачивает на \(90\) градусов либо налево, либо направо; и
так далее. Наконец, проехав последний отрезок (также длиной от \(1\) до
\(10^6\)
сантиметров), он останавливается и начинает передавать на Землю
описание своего маршрута.
В итоге Центр Управления получил от «ТцТцПети» следующее сообщение: «Я сделал n передвижений. Сообщаю \(n \ − \ 1\) поворот, который я совершил: последовательность поворотов. В итоге я оказался в точке с координатами \((x, \ y).\) Мне тут нравится. Конец связи.»
И тут-то создатели «ТцТцПети» поняли, что забыли запрограммировать его, чтобы он сообщал длины своих передвижений!
Теперь их интересует хоть какой-нибудь вариант пути «ТцТцПети», который удовлетворяет полученным от него данным. Помогите им.
В первой строке входного файла содержатся три целых числа \(x, \ y, \ n \ (−100 000 \le x, \ y \le 100 000; 1 \le n \le 100 000\)) — конечные координаты «ТцТцПети» и количество передвижений, которые он совершил.
Вторая строка имеет длину \(n \ − \ 1\) и состоит из символов «L» и «R» — это последовательность поворотов, которые совершил «ТцТцПетя». Символ «L» обозначает поворот налево на \(90\) градусов, символ «R» — направо на \(90\) градусов.
Если информация противоречива и двигаться подобным образом робот не мог, выведите в выходной файл слово «Impossible».
В противном случае выведите n целых чисел от \(1\) до \(10^6\) — длины передвижений «ТцТцПети» в сантиметрах, такие что с учетом указанных им поворотов, «ТцТцПетя» заканчивает движение в точке \((x, \ y).\) Числа должны быть разделены пробелами и/или переводами строк.
Поверхность Марса в рамках данной задачи считается плоской.
-2 -1 4 RRR
1 1 2 3
4 1 5 LRRL
Impossible
0 10 1
10