Задача №112872. Maze
Байтазар недавно прочитал интересную историю. Там был какой-то греческий герой, который победил страшного монстра с помощью клубка пряжи, или что-то подобное. Но это не так уж заинтересовало Байтазара — больше всего ему понравилось, что ключевые события происходили в лабиринте. Отныне Байтазар без ума от лабиринтов.
Байтазар рисует лабиринты на квадратных бумажках. Каждый такой план представляет собой многоугольник, стороны которого (т.е. стены лабиринта) параллельны краям бумаги (т.е. осям в декартовой системе координат), и каждые две соседние стороны перпендикулярны друг другу. Байтазар заметил, что если на одной из стен этого лабиринта разместить вход, а затем все время придерживаться правой стены, то можно обойти весь лабиринт и вернуться обратно ко входу.
Во время обхода можно записывать сделанные повороты. Будем писать L, если во время перехода к следующей стене делается поворот налево, и P, если поворот направо. Байтазару интересно, для каких последовательностей из L и P существует лабиринт, который можно обойти, записав именно эту последовательность.
В первой строке записана одна строка длины n ( 1 ≤ n ≤ 100 000 ), состоящая из букв L и P, описывающая повороты.
В группе тестов на половину баллов n ≤ 2500 .
Если нельзя построить лабиринт в соответствии с описанием, следует вывести слово NIE . В противном случае выведите слово TAK , а затем ровно n строк, описывающих стены лабиринта. В i -й из них должно быть два числа x i и y i ( - 10 9 ≤ x i , y i ≤ 10 9 ), разделенных одним пробелом, которые обозначают координаты i -й вершины лабиринта. Вершины должны быть перечислены в порядке их появления по периметру лабиринта против часовой стрелки. Вы можете начать с любой вершины, и вам не нужно указывать расположение двери.
LLLLPPLL
TAK 0 0 2 0 2 2 -1 2 -1 -2 1 -2 1 -1 0 -1