Карта некоторого объекта представляет из себя клетчатое поле, состоящее из n строк и n столбцов. Каждая клетка изначально занята морем, но вы можете засыпать песком некоторые из клеток клетчатого поля таким образом, чтобы на карте образовалось ровно k островов. Объединим набор клеток с песком в остров, если из каждой из них можно добраться до каждой из них, перемещаясь только по клеткам с песком, и переходя из клетки с песком в соседнюю с ней по стороне клетку с песком. Клетки называются соседними по стороне, если у них есть общая горизонтальная или вертикальная сторона. Легко видеть, что разные острова не могут пересекаться по клеткам (иначе бы они в объединении давали больший остров).

Найдите способ засыпать некоторые клетки песком таким образом, чтобы на карте n × n образовалось ровно k островов, либо сообщите, что такого способа не существует.