Двое играют на бесконечной вправо клетчатой ленте, клетки которой пронумерованы слева направо целыми положительными числами. На ленте расположено конечное количество красных фишек (фишек первого игрока) и синих фишек (фишек второго игрока), на каждой клетке либо располагается несколько красных фишек, либо располагается несколько синих фишек, либо вообще нет фишек.
Игроки ходят по очереди. В свою очередь игрок либо пропускает ход, либо берёт одну из своих фишек и перемещает её на соседнюю клетку (с клетки $$$x$$$ можно переместить фишку на клетку $$$x + 1$$$ при любом $$$x$$$ или на клетку $$$x - 1$$$ при $$$x \ge 2$$$). Если на этой соседней клетке нет фишек противника, на этом ход оканчивается; если же там есть хотя бы одна фишка противника, то с этой клетки пропадает по одной фишке каждого из игроков — таким образом, по окончании хода всё ещё не будет двух разноцветных фишек, располагающихся в одной клетке.
Если у обоих игроков кончились фишки, то игра заканчивается вничью. Если только у одного из игроков кончились фишки, то он объявляется проигравшим, а его соперник — победителем. Наконец, если каждый из игроков сделал по $$$10^{100}$$$ ходов, а игра так и не окончилась, то она принудительно заканчивается, и объявляется ничья.
Вам дана начальная расстановка, определите, кто выиграет при правильной игре обоих игроков, и выведите любой оптимальный ход.
Каждый тест состоит из одного или нескольких тестовых случаев. В первой строке находится целое число $$$t$$$ — количество тестовых случаев ($$$1 \le t \le 10^4$$$). Затем одно за другим следуют описания каждого тестового случая.
В первой строке каждого тестового случая находится целое число $$$n$$$ — число непустых клеток, то есть клеток, изначально содержащих хотя бы одну фишку ($$$2 \le n \le 2 \cdot 10^5$$$).
В $$$i$$$-й из следующих $$$n$$$ строк находится два числа $$$x_i$$$, $$$m_i$$$, и символ $$$c_i$$$, обозначающие координату $$$i$$$-й непустой клетки, количество фишек в ней и цвет этих фишек ($$$1 \le x_1 < x_2 < \cdots < x_n \le 10^6$$$; $$$1 \le m_i \le 10^6$$$; $$$c_i \in \{\mathtt{R}, \mathtt{B}\}$$$). Гарантируется, что на поле есть хотя бы по одной фишке каждого из цветов.
Гарантируется, что сумма значений $$$n$$$ по всем тестовым случаям не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите:
Вы можете выводить каждую букву вывода в любом регистре (заглавном или строчном): так, строки «First», «FIRST», «fiRST» при проверке будут считаться эквивалентными.
1021 1 R2 1 B21 1 B2 1 R21 2 B4 1 R41 1 B2 1 R4 3 B6 1 R21 2 B3 1 R21 2 B2 1 R21 1 R2 2 B21 2 R3 1 B31 1 R2 1 R4 1 B21 2 R2 1 B
Draw 0 0 Draw 2 - Draw 4 - Draw 2 - Draw 0 0 Draw 2 + Second Draw 0 0 Draw 2 - First 1 +
В последнем примере кроме хода «1 +», возможен лишь один другой ход — а именно «0 0» (пропуск хода). Впрочем, это ничейный ход, так что он не будет принят.