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

Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении. Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того, кто с кем сидит рядом.

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

Желая сделать заседание клуба как можно более интересным, Иван Петрович решил разместить участников за круглым столом таким образом, чтобы как можно больше членов клуба приняло активное участие в обсуждении.

Требуется написать программу, которая по заданным числам m и n выведет такой способ размещения m мальчиков и n девочек за круглым столом, при котором максимальное количество членов клуба будет активно участвовать в обсуждении.

Вы по-прежнему работаете под руководством д.б.н., проф. О.Б. Ломова и изучаете интеллект обезьян. Ваши подопечные уже очень далеко ушли от столь элементарной задачи, как сбор квадрата. Теперь вы работаете над тем, чтобы обучить их намного более сложной задаче. Вы по-прежнему даёте обезьянам набор из \(N\) палочек, но на этот раз вы хотите, чтобы они собрали из этих палочек треугольник.

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

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

Юный программист решил придумать собственную игру. Игра происходит на поле размером \(N \times N\) клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.

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

Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.

3
DDD
DDC
DDC

111
111
112

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

11111
11111
12222
22222
22222