eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ленточка 3

Ленточка 3

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Расположенную вертикально прямоугольную бумажную ленточку с закреплённым нижним концом стали складывать следующим образом:

  • на первом шаге её согнули пополам так, что верхняя половина легла на нижнюю либо спереди (P-сгибание) либо сзади (Z-сгибание);

  • на последующих n-1 шагах выполнили аналогичное действие с получившейся на предыдущем шаге согутой ленточкой, как с единым целым.

Затем ленточку развернули, приведя её в исходное состояние. На ней остались сгибы - рёбра от перегибов, причём некоторые из рёбер оказались направленными выпуклостью к нам (K-рёбра), а некоторые - от нас (O-рёбра). Рёбра пронумеровали сверху вниз числами от 1 до 2^n-1.

Требуется написать программу, которая по заданным строке символов из прописных букв "O" и "K", где положение на i-ом месте символа "O" или "K" определяет тип ребра на расправленной полоске, находит подстроку из прописных "P" и "Z", определяющих последовательность типов сгибаний, посредством которых получена ленточка с этой последовательностью рёбер.

Giriş verilənləri

В первой строке входного файла записано число n - количество сгибаний (n не более 20), во второй строке - строка из 2^n-1 символов "O" или "K", определяющих типы рёбер на расправленной ленточке.

Çıxış verilənləri

В единственную строку выходного файла нужно вывести строку из n символов "P" и "Z", задающих последовательность сгибаний. Если такой последовательности сгибаний не существует, то вывести в файл NO.

Nümunə

Giriş verilənləri #1
2
OOK
Çıxış verilənləri #1
PZ