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

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

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

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

«Соединение точек» – это игра для одного игрока. Игровое поле строится следующим образом. Выбираются два целых числа, каждое из которых больше 2, которые обозначаются \(g\) и \(r\). Затем на плоскости рисуются четыре точки в вершинах квадрата, две верхние из них становятся зелеными точками, а две нижние – красными. Далее внутри квадрата рисуются зеленые и красные точки таким образом, что никакие три точки, включая вершины квадрата, не лежат на одной прямой. Процесс продолжается до тех пор, пока общее количество зеленых точек не станет равным \(g\), а количество красных точек – равным \(r\).

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

Будем считать, что две точки \(u\) и \(v\) принадлежат одной компоненте, если от \(u\) до \(v\) можно дойти по нарисованным отрезкам.

Цель игры – соединить все зеленые точки в одну компоненту с помощью (\(g\) – 1) отрезков, а все красные точки – в другую компоненту с помощью (\(r\) – 1) отрезков. Можно доказать, что при вышеописанном способе расположения точек всегда существует способ выиграть игру.

Вам будет задано квадратное игровое поле со стороной \(s\), а также \(g\) зелеными и \(r\) красными точками. Координаты точек задаются парами целых чисел (\(x_i\), \(y_i\)). Зеленые точки пронумерованы числами от 1 до \(g\) так, что верхняя левая точка (0, \(s\)) имеет номер 1, верхняя правая точка (\(s\), \(s\)) – номер 2, а остальные точки – номера от 3 до \(g\) (в произвольном порядке). Красные точки пронумерованы числами от 1 до \(r\) так, что нижняя левая точка (0, 0) имеет номер 1, нижняя правая точка (\(s\), 0) – номер 2, а остальные точки – номера от 3 до \(r\) (в произвольном порядке).

Байтмен владеет красивейшим садом в Байттауне, в котором он посадил n роз. Пришло лето, и цветы выросли большими и красивыми. Байтмен понял, что он не в состоянии самостоятельно ухаживать за всеми розами, и решил нанять двух садовников в помощь. В этом случае ему нужно выбрать две прямоугольные области, чтобы каждый из садовников ухаживал за розами в одной их них. Области не должны пересекаться, и в каждой должно быть ровно \(k\) роз.

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

Сад представляет собой прямоугольник длиной \(l\) метров и шириной \(w\) метров, который разделен на \(l\)·\(w\) одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (\(x\),\(y\)), удовлетворяющие ограничениям 1 <= \(x\) <= \(l\), 1 <= \(y\) <= \(w\). В каждом единичном квадрате может содержаться любое количество роз.

Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (\(l_1\),\(w_1\)), (\(l_1\),\(w_2\)), (\(l_2\),\(w_1\)) и (\(l_2\),\(w_2\)) (для 1 <= \(l_1\) <= \(l_2\) <= \(l\) и 1 <= \(w_1\) <= \(w_2\) <= \(w\)):

• содержит все единичные квадраты с координатами (\(x\),\(y\)), которые удовлетворяют условию \(l_1\) <= \(x\) <= \(l_2\) и \(w_1\) <= \(y\) <= \(w_2\), и
• имеет периметр 2 · (\(l_2\)−\(l_1\)+1)+ 2 · (\(w_2\)−\(w_1\)+1).

Две прямоугольных области не должны пересекаться, то есть, они не должны иметь ни одного общего квадрата. Даже если они имеют общую сторону или её часть, они ограждаются разными заборами.

Рассмотрим неубывающую последовательность \(s_1\), ..., \(s_n\) + 1 ( \(s_i\) <= \(s_i\) + 1 для 1 <= \(i\) <= \(n\) ). Последовательность \(m_1\), ..., \(m_n\), в которой каждый член определен как \(m_i\) = ½ * ( \(s_i\) + \(s_i\) + 1 ) для 1 <= \(i\) <= \(n\), назовем “средней последовательностью” для последовательности \(s_1\), ... \(s_n\) + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из \(n\) целых чисел \(m_1\), ..., \(m_n\) необходимо вычислить количество всех неубывающих последовательностей из \(n\) + 1 целых чисел \(s_1\), ..., \(s_n\) + 1, для которых заданная последовательность \(m_1\), ..., \(m_n\) является средней последовательностью.