По вечерам Рома любит играть в онлайн-покер на одном из популярных сайтов. Игры на этом сайте проходят в странном формате: играют всегда ровно два игрока, ставок нет, а победитель забирает у проигравшего 1 виртуальный бурль.
Прошлым вечером Рома зашёл на сайт и начал играть. Он решил, что потратит за вечер не более k виртуальных бурлей — он прекратит игру, как только количество проигрышей превысит количество выигрышей на k. Также Рома выходит из игры, если он выиграет достаточно за вечер — а именно, если количество выигрышей превысит количество проигрышей на k.
На следующее утро Рома нашёл лист, на котором была записана последовательность результатов игр. Рома точно не помнит порядок игр, и часть результатов записана слишком неразборчиво, поэтому он не может вспомнить, выиграл он или проиграл k бурлей.
Последовательность, записанная Ромой — это строка s, состоящая из символов W (Рома выиграл соответствующую игру), L (Рома проиграл), D (Рома сыграл вничью) и ? (результат игры неизвестен). Рома хочет восстановить по ней любую правильную последовательность результатов игр, заменив все символы ? на W, L или D. Последовательность результатов игр называется правильной, если выполняются следующие условия:
- В конце игры количество выигрышей и проигрышей Ромы различаются ровно на k;
- Нет таких партий, перед которыми количество выигрышей и проигрышей Ромы различались ровно на k.
Помогите Роме, восстановив любую последовательность, удовлетворяющую этим условиям.
Выходные данные
Если правильной последовательности, которая может быть получена из s заменой всех символов ? на символы W, L или D, не существует, выведите NO.
Иначе выведите эту последовательность. Если таких последовательностей несколько, выведите любую из них.