Это интерактивная задача.

Саша и Женя играют в «Речной бой». В этой игре у каждого игрока есть поле — полоска из $$$20$$$ клеток — которое держится в секрете от другого игрока. Поле Саши белое, а поле Жени чёрное.

В начале игры игрок ставит на своё поле четыре корабля: по одному кораблю из одной, двух, трёх и четырёх клеток. Клетки каждого корабля должны следовать на поле подряд, а клетки различных кораблей не могут быть соседними. Вот пример начальной расстановки кораблей: 00022033300000444401. Здесь цифры 1–4 соответствуют клеткам кораблей такой длины, а нули — пустые клетки.

Далее игроки делают ходы по очереди. Начинает Саша. В свой ход игрок выбирает несколько клеток на поле противника, чтобы одновременно атаковать эти клетки. Игрок может выбрать столько клеток, сколько их в его самом длинном не потопленном корабле, или любое меньшее их количество. Корабль потоплен, если все его клетки уже атакованы. Например, на первом ходу Саша может выбрать четыре клетки для атаки: ????!???!!?????????!. Здесь вопросительные знаки — клетки на поле Жени, про которые Саша ничего не знает, а восклицательные знаки — клетки, выбранные для атаки.

После выбора противник должен рассказать, что было в каждой атакованной клетке — они могли быть пусты или содержать части кораблей. Например, Женя могла ответить на атаку Саши так: ????0???44?????????1. Это означает, что в левой атакованной клетке было пусто, в двух средних были части корабля длины $$$4$$$, а в самой правой — единственная часть корабля длины $$$1$$$. Теперь Женин корабль длины $$$1$$$ потоплен, так как все его клетки атакованы, а корабль длины $$$4$$$ ещё не потоплен, ведь атакованы только две из его четырёх клеток. Следующей ходит Женя, и она может также выбрать четыре клетки для атаки.

Выигрывает тот, кто первым потопит все четыре корабля противника. После этого победитель показывает своё поле противнику, чтобы тот мог убедиться, что корабли на нём расставлены по правилам.

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

Женя — на самом деле тоже робот, но она программируемая. Напишите программу для Жени, чтобы победить Сашу $$$50$$$ раз! В этой задаче $$$50$$$ тестов, в каждом из них нужно одержать победу. Поведение Саши в каждом тесте выбрано случайно, как написано выше, но зафиксировано заранее и одинаково для всех проверок на этом тесте.

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

Изначально каждый игрок ничего не знает про поле другого. Поле в таком случае записывается как «color ????????????????????», где color — это «black» для чёрного поля (Саши) и «white» для белого поля (Жени). Клетки, выбранные для атаки, будут обозначаться восклицательными знаками («!»). После атаки клетки, которые оказались пустыми, обозначаются нулями («0»), а клетки, в которых находятся части кораблей — цифрой, равной размеру корабля («1–4»). При следующих ходах клетки, атакованные ранее, всё так же содержат цифры, а не атакованные всё так же содержат вопросительные знаки — даже если цифру на клетке уже можно восстановить однозначно. Поле всегда состоит ровно из $$$20$$$ клеток.

В ход Саши сначала прочитайте строку вида «black ...» — чёрное поле, как о нём известно Саше, с выбранными клетками для атаки (их будет не больше, чем в самом большом не потопленном корабле Саши). Затем выведите строку вида «black ...» — то же чёрное поле, но во всех выбранных для атаки клетках отметьте, частью какого корабля они являются.

В ход Жени сначала выведите строку вида «white ...» — белое поле, как о нём известно Жене, с выбранными клетками для атаки (их должно быть не больше, чем в самом большом не потопленном корабле Жени). Затем прочитайте строку вида «white ...» — то же белое поле, но во всех выбранных для атаки клетках будет отмечено, частью какого корабля они являются.

Если все корабли Жени потоплены, Саша выводит строку вида «white ...» — расстановку кораблей на белом поле без вопросительных и восклицательных знаков. Гарантируется, что Саша выбрал её в начале игры, и каждая строка, выведенная программой жюри, согласована с этой расстановкой. После этого проверка на тесте завершается с вердиктом «Wrong answer».

Если все корабли Саши потоплены, Женя должна вывести строку вида «black ...» — расстановку кораблей на чёрном поле без вопросительных и восклицательных знаков. Каждая строка, выведенная решением, должна быть согласована с этой расстановкой. Если это так, проверка на тесте завершается с вердиктом «OK», если нет — с вердиктом «Wrong answer». Как можно заметить, Саша никак не проверяет, что Женя выбрала расстановку в самом начале игры, а не ставила корабли во время ответов.

После вывода каждой строки, чтобы не получить вердикт «Idleness limit exceeded», следует вывести перевод строки и очистить буфер вывода. Последнее можно сделать, например, вызовом fflush (stdout) в C или C++, sys.stdout.flush () в Python, flush (output) в Pascal или System.out.flush () в Java.