В организации Alternative Cake Manufacturing (ACM) работает n сотрудников. Сейчас там проводится очень важное голосование, и все ведущие мировые СМИ пытаются спрогнозировать его результат.
Так получилось, что каждый из сотрудников имеет ярко выраженные политические взгляды и принадлежит либо к фракции депубликанцев, либо к фракции ремократов, и каждой фракции выгоден свой результат голосования. Процедура голосования устроена крайне необычно:
- Каждый из n сотрудников высказывается по очереди, начиная с сотрудника номер 1 и заканчивая сотрудником номер n. При этом если к моменту, когда сотруднику пора высказаться, его уже лишили права голоса, то он просто пропускает свой ход (и уже никак не участвует в голосовании в последствии).
- Высказывание сотрудника состоит в том, чтобы лишить права голоса любого другого сотрудника или ничего не сделать. Лишать права голоса можно как тех кто уже высказался, так и тех, кому только предстоит высказаться. Лишение права голоса действует в течение всего процесса голосования.
- Когда все сотрудники выскажутся, процедура повторяется: снова по очереди высказываются все от сотрудника 1 до сотрудника n, кто ещё не лишился права голоса.
- Повторения процедуры происходят до тех пор, пока не останется только один сотрудник с правом голоса, то он в одиночку решает исход голосования. Разумеется, он принимает решение в пользу своей фракции.
Зная порядок голосования и то, что все сотрудники действуют оптимально (и знают порядок голосования и кто принадлежит какой фракции), вы должны предсказать, какая фракция одержит верх.
Выходные данные
Выведите «D», если на голосовании будет принято решение, устраивающее фракцию депубликанцев, и «R», если ремократов.
Примечание
Рассмотрим один из вариантов голосования:
- 1-й сотрудник лишает голоса сотрудника 5.
- 2-й сотрудник лишает голоса сотрудника 3.
- 3-й сотрудник пропускает ход, так как его лишил голоса сотрудник 2.
- 4-й сотрудник лишает голоса сотрудника 2.
- 5-й сотрудник пропускает ход, так как его лишил голоса сотрудник 1.
- 1-й сотрудник опять высказывается и лишает голоса сотрудника 4.
- Только сотрудник 1 остался с правом голоса, поэтому голосование заканчивается принятием решения в пользу фракции депубликанцев.