eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пешки

Пешки

Карлу и Нафану совершенно надоела игра в шахматы; это слишком легко! Они придумали свою собственную игру, которая, несомненно, является большим испытанием интеллекта.

Игра происходит на доске размером n на m квадратов. Сначала белые и черные пешки размещаются квази-случайно на доске со следующим ограничением: в каждом столбце имеется одна белая и одна черная пешка, причем белая пешка располагается ниже черной.

Каждый игрок по очереди делает ход одной из своих пешек. Пешке разрешено перемещаться только на одну клетку вперед, при условии, что этот квадрат пуст. "Вперед" означает в направлении противника, так что белые пешки двигаются вверх, а черные двигаются вниз. Кроме того, пешка на первой строке, то есть белая пешка в нижнем ряду или черная пешка в верхнем ряду, также может перемещаться два квадрата вперед при условии, что оба квадрата пусты. В отличие от обычных шахмат, пешки никогда не удаляются из доски и никогда не меняют колонку.

prb8331.gif

Например, на позиции выше Белые (игрок белыми пешками) могут совершить восемь ходов: на одну позицию пешками с b1, d2, f5 и h2, и на две позиции пешками с c1 и g1. Пешки на a6 и e1 передвигаться не могут.

В конечном счете пешки встретятся в каждом столбце, и ни один из игроков не сможет сделать ход. В этом случае игра заканчивается, и победителем является игрок, совершивший последний ход.

Как обычно, Белые делают первый ход. Кто выиграет при правильной игре для заданной стартовой позиции?

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

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

  • первая строка содержит числа n и m (3n20 and 1m20) - количество строк и столбцов на доске.
  • следующие n строк содержат по m символов, задающих начальное состояние доски перед игрой:

    'W' - белая пешка.

    'B' - черная пешка.

    '.' - пустая клетка.

Каждая колонка содержит в точности одну 'W' и одну 'B', где 'W' расположено под 'B'.

В каждом тесте начальная позиция такова что Белые могут совершить хотя бы один ход.

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

Для каждого теста вывести в отдельной строке "White wins" если Белые могут выиграть при оптимальной игре и "Black wins" если у Черных имеется выигрышная стратегия.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
8 8
.....BB.
B.......
W......B
...B.W..
..B.....
.B......
...WB..W
.WW.W.W.
6 4
....
B..B
....
.B.W
W.B.
.WW.
5 3
...
BBB
...
WW.
..W
4 6
.BBB.B
B...B.
...W..
WWW.WW
7 7
.B.B..B
.......
..B.B..
B....B.
.......
...WW.W
WWW..W.
Вихідні дані #1
Black wins
Black wins
White wins
White wins
Black wins
Джерело 2014 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Problem E