Ленточка 2
Расположенную вертикально прямоугольную бумажную ленточку с закреплённым нижним концом стали складывать следующим образом:
на первом шаге её согнули пополам так, что верхняя половина легла на нижнюю либо спереди (P-сгибание) либо сзади (Z-сгибание);
на последующих n-1 шагах выполнили аналогичное действие с получившейся на предыдущем шаге согнутой ленточкой, как с единым целым.
Затем ленточку развернули, приведя её в исходное состояние. На ней остались сгибы - рёбра от перегибов, причём некоторые из рёбер оказались направленными выпуклостью к нам (K-рёбра), а некоторые - от нас (O-рёбра). Рёбра пронумеровали сверху вниз числами от 1 до 2^n-1.
Требуется написать программу, которая по заданным строке символов из прописных букв "P" и "Z", определяющей последовательность типов сгибаний, и номерам рёбер сообщает тип этих рёбер, получившийся после этой последовательности операций.
Входные данные
Входной файл содержит в первой строке число n - количество сгибаний ленточки (n не более 60), во второй строке - набор n символов из прописных латинских букв "P" и "Z". Третья строка содержит в начале число k - количество рассматриваемых рёбер (не более 10), а далее их номера (числа от 1 до 2^n-1).
Выходные данные
В единственную строку выходного файла нужно вывести k символов (прописные латинские буквы "K" или "O") - типы рассматриваемых рёбер.