| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 10 | 9 | 5 | 83.333% |
Робот-марсоход <<ТцТцПетя>> двигается по поверхности Марса как ему вздумается, отправляя на Землю информацию о своих передвижениях.
<<ТцТцПетя>> пользуется следующей системой координат: начало координат совпадает с его начальным положением, ось $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