class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 求出最终获胜帮派的名称
     * @param s string字符串
     * @return string字符串
     */
    string predictVictory(string s) {
        queue<char> red, dark;
        int n = s.size();

        for (int i = 0; i < n; ++i) {
            if (s[i] == 'R') {
                red.push(i);
            } else {
                dark.push(i);
            }
        }

        while (!red.empty() && !dark.empty()) {
            int r = red.front();
            red.pop();
            int d = dark.front();
            dark.pop();

            if (r < d) {
                red.push(r + n);
            } else {
                dark.push(d + n);
            }
        }

        return red.empty() ? "Dark" : "Red";
    }
};