625. Dota2 Senate

Senators from two parties, 'R' (Radiant) and 'D' (Dire), take turns in a round-based process. In order, each senator may ban the next opposing senator from voting; banned senators are skipped. The process loops until only one party remains. Given the senate string, return the winning party: 'Radiant' or 'Dire'. The input is JSON {senate}.

Input: JSON {senate}.

Output: String — 'Radiant' or 'Dire'.

Examples

Input: {"senate":"RD"}
Output: Radiant
Explanation: R bans D first.

Input: {"senate":"RDD"}
Output: Dire
Explanation: The two D senators prevail.

Input: {"senate":"R"}
Output: Radiant
Explanation: Only Radiant remains.

Constraints

• 1<=|senate|<=10^4

Asked by