e-olymp
Məsələlər

Робот

Робот

Робот-марсоход "ТцТцПетя" двигается по поверхности Марса как ему вздумается, отправляя на Землю информацию о своих передвижениях.

"ТцТцПетя" пользуется следующей системой координат: начало координат совпадает с его начальным положением, ось OY направлена в сторону, в которую он направлен в начальный момент времени (при высадке на Марс).

prb1493 Передвигается "ТцТцПетя" следующим образом: после высадки на Марс он проезжает вперед какое-то целое число сантиметров, от 1 до 106; затем поворачивает на 90 градусов либо налево, либо направо; после чего снова проезжает вперед от 1 до 106 сантиметров; и снова поворачивает на 90 градусов либо налево, либо направо; и так далее. Наконец, проехав последний отрезок (также длиной от 1 до 106 сантиметров), он останавливается и начинает передавать на Землю описание своего маршрута.

В итоге Центр Управления получил от "ТцТцПети" cледующее сообщение: "Я сделал n передвижений. Сообщаю n-1 поворот, который я совершил: последовательность поворотов. В итоге я оказался в точке с координатами (x, y). Мне тут нравится. Конец связи."

И тут-то создатели "ТцТцПети" поняли, что забыли запрограммировать его, чтобы он сообщал длины своих передвижений!

Теперь их интересует хоть какой-нибудь вариант пути "ТцТцПети", который удовлетворяет полученным от него данным. Помогите им.

Входные данные

В первой строке входного файла содержатся три целых числа x, y, n (-100000x, y100000; 1n100000) — конечные координаты "ТцТцПети" и количество передвижений, которые он совершил.

Вторая строка имеет длину n-1 и состоит из символов "L" и "R" — это последовательность поворотов, которые совершил "ТцТцПетя". Символ "L" обозначает поворот налево на 90 градусов, символ "R" — направо на 90 градусов.

Выходные данные

Если информация противоречива и двигаться подобным образом робот не мог, выведите в выходной файл слово "Impossible".

В противном случае выведите n целых чисел от 1 до 106 — длины передвижений "ТцТцПети" в сантиметрах, такие что с учетом указанных им поворотов, "ТцТцПетя" заканчивает движение в точке (x, y). Числа должны быть разделены пробелами и/или переводами строк.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
Sample 1
-2 -1 4
RRR

Sample 2
5 1 5
LRRL

Sample 3
0 10 1
Çıxış verilənləri
Sample 1
1 1 2 3

Sample 2
Impossible

Sample 3
10

Şərh: поверхность Марса в рамках данной задачи считается плоской.