Сенат Dota2

В мире Dota2 существуют две фракции: Radiant и Dire.

Сенат Dota2 состоит из сенаторов, принадлежащих к этим двум фракциям. Сейчас Сенат хочет принять решение об изменении в игре Dota2. Голосование происходит в виде пошаговой процедуры. В каждом раунде каждый сенатор может воспользоваться одним из двух прав:

• Запретить право голоса другому сенатору: сенатор может лишить другого сенатора всех его прав в текущем и всех последующих раундах.
• Объявить победу: если сенатор видит, что все оставшиеся сенаторы с правом голоса принадлежат его фракции, он может объявить победу и решить вопрос в пользу своей фракции.

Дана строка senate, представляющая принадлежность сенаторов к фракциям. Символы 'R' и 'D' обозначают фракции Radiant и Dire соответственно. Если всего n сенаторов, то длина строки равна n.

Процедура идёт по раундам от первого сенатора до последнего в заданном порядке. Она продолжается, пока не будет объявлена победа одной из фракций. Все сенаторы, лишённые прав, пропускаются и больше не действуют.

Считайте, что каждый сенатор действует оптимально и в интересах своей фракции. Определите, какая фракция в итоге объявит победу и изменит игру Dota2. Выведите "Radiant" или "Dire".

Пример 1:

Ввод: senate = "RD"
Вывод: "Radiant"

Объяснение:

Первый сенатор — из Radiant, он запрещает право следующему сенатору.

Второй сенатор больше не может действовать.

Во втором раунде первый сенатор — единственный, кто может голосовать, и объявляет победу.

Пример 2:

Ввод: senate = "RDD"
Вывод: "Dire"

Объяснение:

Первый сенатор — Radiant — запрещает право следующему сенатору (Dire).

Второй сенатор (Dire) лишён прав.

Третий сенатор — Dire — запрещает право первому сенатору (Radiant).

Во втором раунде третий сенатор остаётся единственным с правом голоса и объявляет победу.

Ограничения:

• n == senate.length
• 1 ≤ n ≤ 10⁴
• senate[i] = 'R' или 'D'