Игра в аннигиляцию
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Двое играют на бесконечной вправо клетчатой ленте, клетки которой пронумерованы слева направо целыми положительными числами. На ленте расположено конечное количество красных фишек (фишек первого игрока) и синих фишек (фишек второго игрока), на каждой клетке либо располагается несколько красных фишек, либо располагается несколько синих фишек, либо вообще нет фишек.

Игроки ходят по очереди. В свою очередь игрок либо пропускает ход, либо берёт одну из своих фишек и перемещает её на соседнюю клетку (с клетки $$$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$$$.

Выходные данные

Для каждого тестового случая выведите:

В первом и третьем случае (когда первый игрок не проигрывает) также выведите любой выигрышный или ничейный ход (то есть ход, после которого при правильной игре второго игрока останется возможность выиграть или свести игру вничью) в формате «$$$x$$$ $$$d$$$», где $$$x$$$ — координата красной фишки, которой следует походить первому игроку, а $$$d \in \{\texttt{-}, \texttt{+}\}$$$ — направление хода («-» означает, что фишку следует переместить в клетку $$$x - 1$$$, а «+» означает, что в клетку $$$x + 1$$$). Если вы предлагаете, чтобы первый игрок пропустил ход, выведите «0 0».

Вы можете выводить каждую букву вывода в любом регистре (заглавном или строчном): так, строки «First», «FIRST», «fiRST» при проверке будут считаться эквивалентными.

Пример

Входные данные
10
2
1 1 R
2 1 B
2
1 1 B
2 1 R
2
1 2 B
4 1 R
4
1 1 B
2 1 R
4 3 B
6 1 R
2
1 2 B
3 1 R
2
1 2 B
2 1 R
2
1 1 R
2 2 B
2
1 2 R
3 1 B
3
1 1 R
2 1 R
4 1 B
2
1 2 R
2 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» (пропуск хода). Впрочем, это ничейный ход, так что он не будет принят.