Морской бой

В рамках Чемпионата Урала планируется проведение турнира стратегий по игре <<Морской бой 1D>>.

Игра проходит на поле, которое представляет собой прямоугольник размером $1 \times N$ клеток. На поле расставляются $T$ кораблей, каждый из которых имеет вид прямоугольника размером $1 \times K$ клеток. Расстановка кораблей на поле является допустимой, если различные корабли не имеют общих клеток и разделены хотя бы одной пустой клеткой. Игровая программа осуществляет выстрелы в клетки поля, а сервер сообщает, является ли выстрел промахом или попаданием в корабль.

В процессе игры про некоторые клетки становится известно, что при любой допустимой расстановке кораблей они принадлежат какому-либо из кораблей. Назовём такие клетки заведомо занятыми.

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

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

• $N \le 100\\,000$

Игра происходит на поле из $8$ клеток, на котором расставляются $2$ корабля, состоящие из $3$-х клеток каждый. Все допустимые расстановки кораблей приведены на рис. 1. Клетки, отмеченные <<#>>, заведомо заняты. Таких клеток $4$.

Рис. 1. Допустимые расстановки кораблей в начале игры.

Первый выстрел производится в клетку с номером $4$. Это выстрел считается промахом, остаются допустимыми расстановки кораблей, приведенные на рис. 2. Теперь $5$ клеток заведомо заняты.

Рис 2. Допустимые расстановки кораблей после первого выстрела.

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