Блиц Доска

В этой задаче следует найти конечную позицию в игре на квадратной доске.

Рассмотрим игру на квадратной доске, разделенной на 8×8 квадратных ячеек. Изначально доска пустая. Два игрока совершают ходы друг за другом. Первый играет белыми, второй черными. Ход состоит в передвижении или прыжке фишки игрока.

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

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

Оба игрока согласились совершать хода в соответствии со значениями, которые выдает случайный генератор чисел: первое случайное число определяет ход первого игрока, второе число - ход второго игрока, третье число - ход первого игрока и так далее.

Вам заданы параметры a, c и s линейного конгруэнтного псевдослучайного генератора 64-битового знакового целочисленного типа. Этот генератор работает следующим образом: для получения следующего случайного числа выполняется присваивание s_new := s_old ∙ a + c, результат округляется до 64-битового знакового целого, который считается новым значением s и является следующим случайным числом.

Ход определяется числом p, полученного из 11 старших бит случайного числа (другими словами p - результат целочисленного деления s на 2^53, округленное в направлении нуля). Если p < 0, ходом является прыжок. Иначе ходом является передвижение, биты 8 (умноженное на 1) и 9 (умноженное на 2) формируют направление (0 - вверх, 1 - влево, 2 - вниз, 3 - вправо), а биты от 0 до 7 описывают, какие из восьми ячеек будут содержать новые фишки. Ячейки нумеруются с 0 до 7 сверху вниз и слева направо (в зависимости от направления).

По заданным числам a, c и s, а также количеству полуходов n найдите конечную позицию на доске. Полуходом называется ход одного из двух участников. Гарантируется, что n четно. Гарантируется, что во всех тестах кроме приведенного примера, тройка чисел a, c и s выбирается равномерно случайно среди всех таких троек, которыми задается линейный конгруэнтный генератор, имеющий период в точности 2^64.

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

Первая строка содержит целое число n - количество полуходов в игре, а также значения a, c и s - параметры генератора случайных чисел (2 ≤ n ≤ 30 000 000, n четно, -2^63 ≤ a, c, s < 2^63, период генератора в точности 2^64).

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

Вывести восемь строк, каждая из которых содержит восемь символов: состояние доски после выполнения всех ходов. Пустые клетки следует обозначать “.”, белые фишки обозначать символом “W”, а черные символом “B”.

Примеры

Примечание

В следующей таблице приведены значения s, значения p и значения специальных бит p.

Внизу на картинке показаны все промежуточные состояния доски для приведенного примера.