#include "testlib.h"
#include <ranges>
 
const uint32_t MAX_T = 10'000;
const uint32_t MAX_N = 200'000;
const uint32_t MAX_TOTAL_N = 200'000;
const uint32_t MAX_X = 1'000'000;
const uint32_t MAX_M = 1'000'000;
 
const pattern RED_OR_BLUE_TEMPLATE("[RB]");
const pattern RED_TEMPLATE("[R]");
const pattern DIRECTION_TEMPLATE("[\\-0\\+]");
const pattern RIGHT_TEMPLATE("+");
const pattern LEFT_TEMPLATE("-");
const pattern RESULT_LOWERCASE_TEMPLATE("(first|draw|second)");
const pattern FIRST_LOWERCASE_TEMPLATE("first");
const pattern DRAW_LOWERCASE_TEMPLATE("draw");
const pattern ANY_TEMPLATE("[^]*");
 
enum Color {
    RED, BLUE
};
 
std::string to_string(const Color color) {
    return color == RED ? "red" : "blue";
}
 
struct Cell {
    uint32_t coordinate;
    uint32_t number_of_chips;
    Color color;
 
    std::strong_ordering operator<=>(const Cell other) const {
        if (coordinate != other.coordinate || number_of_chips == other.number_of_chips && color == other.color)
            return coordinate <=> other.coordinate;
        else
            return std::strong_ordering::equivalent;
    }
    bool operator==(const Cell& other) const = default;
};
 
enum Direction {
    LEFT, SKIP, RIGHT
};
 
std::string to_string(Direction direction) {
    if (direction == LEFT)
        return "LEFT";
    else if (direction == SKIP)
        return "SKIP";
    else
        return "RIGHT";
}
 
Direction read_direction(InStream& in, const std::string& variable_name) {
    std::string direction = in.readToken(DIRECTION_TEMPLATE, variable_name);
    if (RIGHT_TEMPLATE.matches(direction))
        return RIGHT;
    else if (LEFT_TEMPLATE.matches(direction))
        return LEFT;
    else
        return SKIP;
}
 
struct Move {
    uint32_t coordinate;
    Direction direction;
};
 
Move read_move(InStream& in, const uint32_t test_number) {
    Move move;
    move.coordinate = in.readInt(0, MAX_X, std::format("move[{}].coordinate", test_number));
    move.direction = read_direction(in, std::format("move[{}].direction", test_number));
    return move;
}
 
struct ChipsStorage {
    uint64_t total_chips = 0;
    std::vector<Cell> cells;
    
    ChipsStorage() = default;
    
    ChipsStorage(const ChipsStorage&) = default;
 
    ChipsStorage&& operator+(const Cell cell) && {
        cells.push_back(cell);
        total_chips += cell.number_of_chips;
        return std::move(*this);
    }
 
    void add_chips(InStream& in, const uint32_t test_number, const uint32_t coordinate, const int32_t chips_delta, const Color color) {
        if (chips_delta == 0) return;
        total_chips += chips_delta;
        std::vector<Cell>::iterator from_cell = std::ranges::find(cells, coordinate, [](const Cell cell) { return cell.coordinate; });
        if (from_cell == cells.end()) {
            in.ensuref(chips_delta > 0, "%s", std::format("no chips in cell {}, but need to remove {} {} chips",
                                                           coordinate, -chips_delta, to_string(color)).c_str());
            cells.push_back({.coordinate = coordinate, .number_of_chips = static_cast<uint32_t>(chips_delta), .color = color});
            return;
        }
        Cell& cell = *from_cell;
        if (cell.color == color) {
            in.ensuref(chips_delta >= -static_cast<int32_t>(cell.number_of_chips), "%s", std::format("only {} {} chips in cell {}, but need to remove {} > {} {} chips",
                                                                                                      cell.number_of_chips, to_string(color), coordinate, -chips_delta, cell.number_of_chips, to_string(color)).c_str());
            if (chips_delta == -static_cast<int32_t>(cell.number_of_chips))
                cells.erase(from_cell);
            else
                cell.number_of_chips += chips_delta;
        } else {
            in.ensuref(chips_delta > 0, "%s", std::format("{} {} chips in cell {}, but need to remove {} {} chips",
                                                           cell.number_of_chips, to_string(cell.color), coordinate, -chips_delta, to_string(color)).c_str());
            if (chips_delta < cell.number_of_chips) {
                cell.number_of_chips -= chips_delta;
                total_chips -= 2 * chips_delta;
            }
            else {
                total_chips -= 2 * cell.number_of_chips;
                uint32_t final_number_of_chips = chips_delta - cell.number_of_chips;
                cells.erase(from_cell);
                if (final_number_of_chips > 0)
                    cells.push_back({.coordinate = coordinate, .number_of_chips = final_number_of_chips, .color = color});
            }
        }
    }
 
    void perform(InStream& in, const uint32_t test_number, const Move& move, const Color color) {
        if (move.direction == SKIP) {
            in.ensuref(move.coordinate == 0, "%s", std::format(R"("{}" move was performed from cell {}, but only 0 is allowed)", to_string(move.direction), move.coordinate).c_str());
            return;
        }
        int32_t coordinate_delta;
        if (move.direction == LEFT) {
            in.ensuref(move.coordinate > 1, "%s", std::format(R"("{}" move was performed from cell {}, but only >1 is allowed)", to_string(move.direction), move.coordinate).c_str());
            coordinate_delta = -1;
        } else
            coordinate_delta = 1;
        add_chips(in, test_number, move.coordinate, -1, color);
        const uint32_t new_coordinate = move.coordinate + coordinate_delta;
        add_chips(in, test_number, new_coordinate, 1, color);
    }
};
 
struct CuriousStatistics {
    uint64_t chips = 0;
    uint32_t non_empty_cells = 0;
    uint32_t wins = 0;
    uint32_t draws = 0;
    uint32_t losses = 0;
 
    CuriousStatistics operator+(const CuriousStatistics& other) {
        chips += other.chips;
        non_empty_cells += other.non_empty_cells;
        wins += other.wins;
        draws += other.draws;
        losses += other.losses;
        return *this;
    }
};
 
enum Result {
    FIRST, DRAW, SECOND
};
 
std::string to_string(const Result result) {
    if (result == FIRST)
        return "First";
    else if (result == DRAW)
        return "Draw";
    else
        return "Second";
}
 
char to_lower_char(char c) {
    return std::tolower(c);
}
 
Result read_result(InStream& in, uint32_t test_number) {
    std::string result = in.readToken(ANY_TEMPLATE, std::format("result[{}]", test_number));
    std::string lowercase_result = result | std::ranges::views::transform(to_lower_char) | std::ranges::to<std::string>();
    in.ensuref(RESULT_LOWERCASE_TEMPLATE.matches(lowercase_result), "%s", std::format("result[{}] is unknown: \"{}\"", test_number, result).c_str());
    if (FIRST_LOWERCASE_TEMPLATE.matches(lowercase_result))
        return FIRST;
    else if (DRAW_LOWERCASE_TEMPLATE.matches(lowercase_result))
        return DRAW;
    else
        return SECOND;
}
 
struct Answer {
    Result result;
    std::optional<Move> move;
};
 
Answer read_answer(InStream& in, const uint32_t test_number) {
    Answer answer{};
    answer.result = read_result(in, test_number);
    if (answer.result != SECOND)
        answer.move = read_move(in, test_number);
    return answer;
}
 
namespace solution {
    struct TwoChipsAdvancement {
        bool positive_over, negative_over, chip_inequality;
        int64_t delta;
    };
 
    template <class T, Color FIRST_MOVER>
    struct TwoChipsIterator {
        using difference_type = int32_t;
        using value_type = TwoChipsAdvancement;
        T::const_iterator positive_iterator, negative_iterator,
                end_positive_iterator, end_negative_iterator;
        uint32_t remaining_positive_chips, remaining_negative_chips;
        bool halt;
 
        bool saw_chip_inequality() const {
            bool positive_over = positive_iterator == end_positive_iterator;
            bool negative_over = negative_iterator == end_negative_iterator;
            bool bigger_positive = negative_over && remaining_positive_chips > 0;
            bool bigger_negative = positive_over && remaining_negative_chips > 0;
            return bigger_positive || bigger_negative;
        }
 
        TwoChipsAdvancement operator*() const {
            bool positive_over = positive_iterator == end_positive_iterator;
            bool negative_over = negative_iterator == end_negative_iterator;
            uint32_t positive_coordinate = !positive_over ? positive_iterator->coordinate : 0;
            uint32_t negative_coordinate = !negative_over ? negative_iterator->coordinate : 0;
            return {
                    .positive_over = positive_over,
                    .negative_over = negative_over,
                    .chip_inequality = saw_chip_inequality(),
                    .delta = (static_cast<int64_t>(positive_coordinate) - static_cast<int64_t>(negative_coordinate)) * std::min<int64_t>(remaining_positive_chips, remaining_negative_chips)};
        }
 
        bool operator==(const TwoChipsIterator& other) const {
            if (halt || other.halt)
                return halt == other.halt;
            return positive_iterator == other.positive_iterator &&
                   negative_iterator == other.negative_iterator &&
                   remaining_positive_chips == other.remaining_positive_chips &&
                   remaining_negative_chips == other.remaining_negative_chips;
        }
 
        TwoChipsIterator& operator++() {
            if (halt)
                throw std::runtime_error("Cannot increment a finished iterator");
            if (remaining_positive_chips <= remaining_negative_chips && positive_iterator != end_positive_iterator) {
                remaining_negative_chips -= remaining_positive_chips;
                remaining_positive_chips = 0;
                ++positive_iterator;
                if (positive_iterator != end_positive_iterator && positive_iterator->color == FIRST_MOVER)
                    remaining_positive_chips = positive_iterator->number_of_chips;
            } else if (remaining_negative_chips <= remaining_positive_chips && negative_iterator != end_negative_iterator) {
                remaining_positive_chips -= remaining_negative_chips;
                remaining_negative_chips = 0;
                ++negative_iterator;
                if (negative_iterator != end_negative_iterator && negative_iterator->color != FIRST_MOVER)
                    remaining_negative_chips = negative_iterator->number_of_chips;
            } else
                halt = true;
            return *this;
        }
 
        TwoChipsIterator operator++(int) {
            TwoChipsIterator other = *this;
            ++*this;
            return other;
        }
    };
 
    template<class T, Color FIRST_MOVER>
    struct ColoredChipStorage {
        const T& cells;
 
        ColoredChipStorage(const T& container) : cells(container) {}
 
        TwoChipsIterator<T, FIRST_MOVER> begin() const {
            return {
                    .positive_iterator = cells.cbegin(),
                    .negative_iterator = cells.cbegin(),
                    .end_positive_iterator = cells.cend(),
                    .end_negative_iterator = cells.cend(),
                    .remaining_positive_chips = cells.begin() != cells.end() && cells.begin()->color == FIRST_MOVER
                                                ? cells.begin()->number_of_chips : 0,
                    .remaining_negative_chips = cells.begin() != cells.end() && cells.begin()->color != FIRST_MOVER
                                                ? cells.begin()->number_of_chips : 0,
            };
        }
 
        TwoChipsIterator<T, FIRST_MOVER> end() const {
            return {
                    .positive_iterator = cells.cend(),
                    .negative_iterator = cells.cend(),
                    .end_positive_iterator = cells.cend(),
                    .end_negative_iterator = cells.cend(),
                    .remaining_positive_chips = 0,
                    .remaining_negative_chips = 0,
                    .halt = true,
            };
        }
    };
 
    struct ColoredSuffixInfo {
        int64_t current_balance = 0;
        bool more_positive = false, more_negative = false, seen_positive_suffix = false, seen_strictly_negative_suffix = false;
 
        ColoredSuffixInfo operator+(const TwoChipsAdvancement two_chips_advancement) && {
            more_positive |= two_chips_advancement.negative_over && two_chips_advancement.chip_inequality;
            more_negative |= two_chips_advancement.positive_over && two_chips_advancement.chip_inequality;
            current_balance += two_chips_advancement.delta;
            if (current_balance >= 1)
                seen_positive_suffix = true;
            if (current_balance <= -2)
                seen_strictly_negative_suffix = true;
            return *this;
        }
    };
 
    template<Color FIRST_MOVER>
    Result find_result(ChipsStorage chips_storage) {
        std::ranges::sort(chips_storage.cells, std::ranges::greater());
        ColoredChipStorage<std::vector<Cell>, FIRST_MOVER> colored_chips(chips_storage.cells);
        ColoredSuffixInfo analysis_result = std::ranges::fold_left(colored_chips, ColoredSuffixInfo{}, std::plus());
        if (analysis_result.more_negative && !analysis_result.seen_positive_suffix)
            return SECOND;
        else if (analysis_result.more_positive && !analysis_result.seen_strictly_negative_suffix)
            return FIRST;
        else
            return DRAW;
    }
}
 
Answer read_and_check_ans(InStream& in, const uint32_t test_number, ChipsStorage chips_storage) {
    Answer answer = read_answer(in, test_number);
    if ((answer.result == SECOND) == answer.move.has_value())
        // never happens
        in.quitf(_fail, "%s", std::format(R"(incorrect answer scan: answer.result == "{}" but answer.move.has_value() == {})",
                                       to_string(answer.result), answer.move.has_value()).c_str());
    if (answer.result == SECOND)
        return answer;
    chips_storage.perform(in, test_number, answer.move.value(), RED);
    Result actual_result = solution::find_result<BLUE>(std::move(chips_storage));
    if (actual_result == FIRST)
        actual_result = SECOND;
    else if (actual_result == SECOND)
        actual_result = FIRST;
    in.ensuref(answer.result == actual_result, "%s", std::format("it is said that move leads to result \"{}\", but actually it leads to \"{}\"",
                                                          to_string(answer.result), to_string(actual_result)).c_str());
    return answer;
}
 
CuriousStatistics processTestCase(const uint32_t test_number) {
    setTestCase(test_number);
    CuriousStatistics statistics{};
    uint32_t n = inf.readInt(2, MAX_N, std::format("n[{}]", test_number));
    statistics.non_empty_cells += n;
    ChipsStorage chips_storage = std::ranges::fold_left(std::ranges::views::iota(static_cast<uint32_t>(1), n + 1) | std::ranges::views::transform([test_number](uint32_t cell_index) {
        Cell cell{};
        cell.coordinate = inf.readInt(1, MAX_X, std::format("x[{}][{}]", test_number, cell_index));
        cell.number_of_chips = inf.readInt(1, MAX_M, std::format("m[{}][{}]", test_number, cell_index));
        std::string color = inf.readToken(RED_OR_BLUE_TEMPLATE, std::format("c[{}][{}]", test_number, cell_index));
        cell.color = RED_TEMPLATE.matches(color) ? RED : BLUE;
        return cell;
    }), ChipsStorage{}, std::plus<>());
    Answer jury_answer = read_and_check_ans(ans, test_number, chips_storage);
    Answer participant_answer = read_and_check_ans(ouf, test_number, chips_storage);
    if (jury_answer.result != participant_answer.result) {
        if (jury_answer.result == FIRST || participant_answer.result == SECOND)
            quitf(_wa, "%s", std::format(R"(Participant achieved "{}" which is worse than jury's "{}")", to_string(participant_answer.result), to_string(jury_answer.result)).c_str());
        else
            quitf(_fail, "%s", std::format(R"(Participant achieved "{}" which is better than jury's "{}")", to_string(participant_answer.result), to_string(jury_answer.result)).c_str());
    }
    if (jury_answer.result == FIRST)
        ++statistics.wins;
    else if (jury_answer.result == DRAW)
        ++statistics.draws;
    else
        ++statistics.losses;
    return statistics;
}
 
int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
    uint32_t T = inf.readInt(1, MAX_T, "T");
    CuriousStatistics statistics = std::ranges::fold_left(std::ranges::views::iota(static_cast<uint32_t>(1), T + 1) | std::ranges::views::transform(processTestCase), CuriousStatistics{}, std::plus());
    quitf(_ok, "%s", std::format("{} chips, {} non-empty cells, {} wins, {} draws, {} losses",
                                 statistics.chips, statistics.non_empty_cells, statistics.wins, statistics.draws, statistics.losses).c_str());
}
