Вывод формулы

Ипполит Матвеевич Воробьянинов ходит вдоль улицы из \(n\) домов, пронумерованных числами от \(1\) до \(n\), и расклеивает афиши. Сначала он наклеил афиши на каждый дом, номер которого делился без остатка на \(a\). Поскольку афиш осталось еще много, вторым проходом он наклеил афиши на каждый дом, номер которого делился без остатка на \(b\). При этом, если на доме уже была наклеена афиша, новую Воробьянинов не клеил. Сколько всего афиш расклеил бывший предводитель дворянства?

Формат входных данных
Три строки содержат три натуральных числа: \(n\) — количество домов на улице, \(a\) и \(b\) — выбранные Воробьяниновым числа. Все числа не превосходят \(10^9\).

Формат выходных данных
Выведите одно неотрицательное целое число — количество расклеенных афиш.

Замечание
В первом примере на улице \(10\) домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на \(2\), то есть на дома с номерами \(2\), \(4\), \(6\), \(8\), \(10\). Вторым проходом он расклеил две афиши на дома, номера которых делятся на \(3\), то есть на дома с номерами \(3\) и \(9\). Дом номер \(6\) он пропустил — на нем афиша уже висит. Всего наклеено \(7\) афиш.

Во втором примере Воробьянинов не наклеит ни одной афиши.

В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на <<первый–\(k\)-й>>.

Как известно, расчёт на <<первый–\(k\)-й>> происходит следующим образом: первые \(k\) человек имеют номера \(1, 2, 3, \ldots, k\), следующие \(k - 1\) человек имеют номера \(k - 1, k - 2, \ldots, 1\), следующие \(k - 1\) человек имеют номера \(2, 3, \ldots, k\) и т.д. Таким образом, расчёт повторяется через каждые \(2k - 2\) позиции. Примеры расчёта приведены в разделе <<Замечание>>.

Мальчик Вася постоянно всё забывает. Например, он забыл позицию, которую занимал в шеренге. Но он помнит число \(k\), описанное выше, номер, который он получил при расчёте, а также, что его позиция в шеренге была не больше \(n\). Другими словами, если Вася стоял на позиции \(y\) в шеренге, то \(y \leq n\). Помогите Васе понять, сколько есть различных позиций в ряду, где он мог стоять.

Формат входных данных
Первая строка содержит одно целое число \(k\) (\(2 \leq k \leq 10^9\)) — характеристика расчёта, описанная в условии.

Вторая строка содержит одно целое число \(x\) (\(1 \leq x \leq k\)) — номер, который Вася получил при расчёте.

Третья строка содержит одно целое число \(n\) (\(x \leq n \leq 10^9\)) — верхнее ограничение на позицию Васи.

Формат выходных данных
Выведите единственное целое число – количество различных позиций, которые подходят под данные ограничения.

Замечание

В первом примере подходят позиции равные \(2, 4, 6, 8, 10\).

Во втором примере подходят позиции равные \(2, 4, 6, 8, 10\).

В третьем примере подходят позиции равные \(3\) и \(7\).

Пример расчёта для \(k = 2\), \(k = 3\) и \(k = 5\):

У Пети есть прямоугольник размера \(a \times b\) с целыми сторонами, хотя бы одна из которых больше \(1\). Он пробует разрезать этот прямоугольник на два прямоугольника с целыми сторонами, сделав разрез, параллельный какой-то из сторон исходного прямоугольника. Затем Петя пытается из двух получившихся прямоугольников сложить какой-то отличный от исходного прямоугольник, при этом он может как угодно поворачивать и двигать эти два прямоугольника. Если у него получается это сделать, то он называет прямоугольник \(a \times b\) интересным.

Обратите внимание, что если два прямоугольника отличаются поворотом на \(90^{\circ}\), то они считаются одинаковыми. Например, прямоугольники \(6 \times 4\) и \(4 \times 6\) считаются одинаковыми.

Таким образом, прямоугольник \(2 \times 6\) является интересным, потому что его можно разрезать на два прямоугольника \(2 \times 3\), после чего из этих двух прямоугольников сложить прямоугольник \(4 \times 3\), который отличается от прямоугольника \(2 \times 6\).

При этом прямоугольник \(2 \times 1\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 1\), а из них можно сложить только прямоугольники \(1 \times 2\) и \(2 \times 1\), которые считаются одинаковыми с исходным.

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

Формат входных данных
Первая и единственная строка содержит одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^9\)) — ограничение на длину сторон прямоугольника.

Формат выходных данных
Выведите одно целое число — количество различных интересных прямоугольников с длинами сторон, не превышающими \(n\).

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.

Замечание

В первом примере только прямоугольник \(2 \times 2\) является интересным: его можно разрезать на два прямоугольника \(1 \times 2\), а из них можно сложить прямоугольник \(1 \times 4\). Обратите внимание, что прямоугольник \(1 \times 1\) не является интересным, потому что хотя бы одна сторона должна быть больше \(1\).

Во втором примере прямоугольники \(2 \times 2\) и \(2 \times 3\) являются интересными. Прямоугольник \(2 \times 3\) можно разрезать на два прямоугольника \(1 \times 3\), а из них можно сложить прямоугольник \(1 \times 6\). Прямоугольник \(3 \times 3\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 3\) и \(2 \times 3\), но из них можно сложить только прямоугольник \(3 \times 3\). Обратите внимание, что прямоугольники \(2 \times 3\) и \(3 \times 2\) считаются одинаковыми, поэтому в ответе их нужно учесть только один раз.

В самом лучшем университете России есть специальный предмет, который называется <<Теория Лени>>. Вы очень любите этот предмет и стараетесь постоянно использовать то, чему вас там научили.

Но, как и везде, на нём есть устный экзамен. Всего есть \(n\) билетов, из которых вы выучили ровно \(a\) (ваша лень не позволяет вам выучить больше).

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

Вы знаете, что до вас отвечали уже \(b\) человек, а это значит, что стопка содержит уже на \(b\) билетов меньше. Так как вас интересует не только <<Теория Лени>>, но и математика (и даже чуть-чуть информатика!), вы хотите узнать, какое минимальное и максимальное количество билетов из оставшихся вы можете знать.

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(1 \leq n \leq 10^9\)) — количество билетов на экзамене.

Вторая строка содержит одно целое число \(a\) (\(1 \leq a \leq n\)) — количество билетов, которые вы выучили.

Третья строка содержит одно целое число \(b\) (\(0 \leq b < n\)) — количество людей, которые уже взяли свой билет до вас.

Формат выходных данных
Вывод вашей программы должен состоять из двух строк.

Первая строка должна содержать единственное целое число — минимальное количество билетов, которое вы можете знать из оставшихся.

Вторая строка должна содержать единственное целое число — максимальное количество билетов, которое вы можете знать из оставшихся.

 

В первом примере давайте считать, что вы знаете билеты с номерами \(1, 2, 3, 4\). Тогда, если люди до вас вытянули билеты с номерами \(1, 2, 3\), то остался только \(1\) билет, который вы знаете. А если люди до вас вытянули билеты с номерами \(4, 5, 6\), то вы знаете \(3\) билета из оставшихся.

Задано четыре числа: \(a\), \(b\), \(c\) и \(d\). Требуется разбить их на две пары, чтобы сумма произведений в этих парах была максимальна.

Например, если заданы числа 2, 3, 4 и 5, то оптимально разбить их на пары \((2, 3)\) и \((4, 5)\), в этом случае искомая сумма равна \(2 \times 3 + 4 \times 5 = 26\).

Формат входных данных
На вход подаются четыре числа: \(a\), \(b\), \(c\) и \(d\). Все числа по модулю не превышают 1000.

Формат выходных данных
Выведите искомую максимальную сумму.

После тяжелого контеста бывает полезно выпить немного кофе. У настоящих программистов есть множество различных сортов кофе, которые постепенно добавляются в одну кружку. При этом мы будем рассматривать кофе с определенной особенностью: разные сорта кофе держатся в кружке <<слоями>> и не перемешиваются.

Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито \(n\) сортов, \(i\)-й сорт характеризуется уровнем крепости \(p_i\) и высотой слоя, который он занимает в кружке, \(h_i\). При этом если \(i < j\), то слой кофе \(i\)-го сорта находится ниже кофе \(j\)-го сорта. Также известно, что высота кружки равна \(\sum\limits_{i=1}^n h_i\), то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.

Для разнообразия иногда хочется получить из такого <<коктейля>> напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как \[P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}\]

Чтобы как-то изменять \(P\), можно

1. выбрать трубочку произвольной высоты \(h\);

2. один или более раз выполнить следующее: погрузить ее в напиток на любую глубину от \(0\) до \(h\) включительно относительно верхнего края кружки (не относительно текущего уровня жидкости) и отпить произвольное (не обязательно целое) количество кофе с того уровня, на который попал нижний конец трубочки.

При выпивании какого-то количества кофе из одного слоя высота этого слоя уменьшается на соответствующую величину, а все верхние слои опускаются на ту же величину вниз.

Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости \(t_i\), и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка \(t_i\).

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(q\) — количество слоев кофе в кружке и количество запросов (\(1 \le n, q \le 2 \cdot 10^5\)).

Следующие \(n\) строк содержат по два целых числа \(p_i\) и \(h_i\) — уровень крепости и высоту \(i\)-го снизу кружки слоя кофе (\(1 \le p_i, h_i \le 10^9\)). Гарантируется, что сумма \(p_i \cdot h_i\) по всем \(i\) не превосходит \(10^{18}\).

В \(i\)-й из следующих \(q\) строк дано единственное целое число \(t_i\), определяющее \(i\)-й запрос (\(1 \le t_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых содержится единственное целое число от \(0\) до \(n\) — ответ \(i\)-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число \(-1\).

 

Замечание
Для примера из условия:

1. В первом запросе, чтобы получить напиток крепости \(1\), достаточно выпить верхние два слоя кофе.

2. Во втором запросе достаточно выпить часть кофе со второго сверху слоя.

3. В третьем запросе понадобится выпить первый и третий слой кофе.

4. В четвертом запросе невозможно добиться уровня крепости \(4\).

Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.

Всего в олимпиаде участвуют \(n\) человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом \(x\) минут. Таким образом первый участник начнёт тур в момент времени \(0\), второй участник начнёт тур в момент времени \(x\), третий — в момент времени \(2 \cdot x\) и так далее.

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

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

Формат входных данных
В первой строке вводится единственное целое число \(n\) (\(1 \le n \le 2 \cdot 10^9\)) — число участников олимпиады.

Во второй строке вводится единственное целое число \(x\) (\(1 \le x \le 2 \cdot 10^9\)) — интервал в минутах между временами начала тура для участников.

В третей строке вводится единственное целое число \(t\) (\(1 \le t \le 2 \cdot 10^9\)) — длительность тура.

Формат выходных данных
В единственной строке выведите одно число — суммарное недовольство всех участников олимпиады.

В первом примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(5\). К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт писать в момент времени \(2\) и закончит в момент времени \(7\). К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно \(2\).

Третий участник начнёт писать тур в момент времени \(4\) и закончит в момент времени \(9\). К этому времени четвёртый участник уже начнёт писать тур, поэтому недовольство третьего будет равно \(1\).

Четвёртый участник начнёт писать тур в момент времени \(6\) и закончит в момент времени \(11\). В момент времени \(9\) уже никто не будет писать тур, поэтому недовольство четвёртого будет равно \(0\).

Таким образом, суммарное недовольство всех участников будет равно \(2+2+1+0=5\).

Во втором примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(2\). К этому моменту второй участник уже будет писать тур, а третий участник как раз начнёт в момент времени \(2\). Поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт в момент времени \(1\) и закончит в момент времени \(3\). К этому моменту только третий участник будет всё ещё писать тур.

Таким образом, суммарное недовольство всех участников будет равно \(2+1=3\).

Миша увлекается компьютерной графикой. Он хочет нарисовать на экране квадрат размером \(n\times n\) пикселей разными цветами.

Монитор Миши поддерживает 26 цветов. Для обозначения цветов будем использовать строчные буквы латинского алфавита от <<a>> до <<z>>. Миша хочет нарисовать каждый пиксель некоторым цветом, который зависит от расстояния от пикселя до ближайшей диагонали.

А именно, клетки на диагоналях квадрата он хочет нарисовать цветом <<a>>, соседние с ними клетки — цветом <<b>>, соседние с ними, но еще не покрашенные — цветом <<c>>, и так далее. После цвета <<z>> Миша снова переходит к цвету <<a>>.

По заданному \(n\) выведите картинку, которая получится у Миши.

Формат входных данных
Входные данные содержат одно целое число \(n\) (\(1 \le n \le 100\)).

Формат выходных данных
Выведите \(n\) строк по \(n\) символов — картинку, которая получится у Миши.

Старшеклассники Андрей и Аня планируют прийти на празднование 1 сентября у первоклассников. Они решили принести конфеты, чтобы раздать ребятам. Им известно, что на празднике будет \(n\) первоклассников. Каждый из старшеклассников готов купить от \(a\) до \(b\) конфет, включительно. Они хотели бы купить в сумме такое число конфет, чтобы их можно было поделить между всеми первоклассниками поровну. Если же такое число конфет купить не получается, то они хотят, чтобы после деления поровну между первоклассниками осталось как можно меньше конфет.

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

Формат входных данных
На ввод подаются три натуральных числа, по одному на строке: \(n\) — число первоклассников, \(a\) и \(b\) — минимальное и максимальное число конфет, которое согласен купить каждый из старшеклассников (\(1 \le n \le 10^9\), \(1 \le a \le b \le 10^9\)).

Формат выходных данных
Выведите два целых числа \(x\) и \(y\) — число конфет, которые купят Андрей и Аня, соответственно.

Валентин выписывает натуральные числа, начиная с 1, в виде лестницы: на первой строке он пишет одно число, на второй — два, на третьей — три, и так далее.

1
2 3
4 5 6
7 8 9 10
...

После этого он стирает все числа на каждой строке, кроме первых \(k\). Если в строке меньше \(k\) чисел, он оставляет их все.

Заданы целые числа \(a\) и \(b\), а также число \(k\). Выведите строки с \(a\)-й по \(b\)-ю, которые получились у Валентина.

Формат входных данных

На ввод подаются три строки: первая содержит число \(a\), вторая содержит число \(b\), третья содержит число \(k\) (\(1 \le a \le b \le 10^9\), \(b - a \le 100\), \(1 \le k \le 100\)).

Формат выходных данных
Выведите строки с \(a\)-й по \(b\)-ю, которые получились у Валентина. Числа в строках разделяйте пробелами.

 

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

Бомбослав заметил, что ребята во дворе не очень изобретательны в своих действиях, и всегда меняют местами левый напёрсток со средним на нечётных действиях (то есть на первом, третьем, пятом и так далее) и средний с правым на чётных действиях (то есть на втором, четвёртом и так далее).

Пронумеруем напёрстки от \(0\) до \(2\) слева направо. То есть левый напёрстком имеет номер \(0\), средний номер \(1\), а правый номер \(2\). Бомбослав не успел увидеть начало игры, но посчитал, что ведущий совершил \(n\) действий и в итоге шарик оказался под напёрстком \(x\). Под каким напёрстком находился шарик в самом начале?

Формат входных данных
В первой строке входных данных записано одно цело число \(n\) (\(1 \leq n \leq 2 \cdot 10^9\)) — количество действий, совершённых ведущим.

Во второй строке записано одно целое число \(x\) (\(0 \leq x \leq 2\)) — номер напёрстка, под которым оказался шарик через \(n\) действий.

Формат выходных данных
Выведите одно целое число от \(0\) до \(2\), означающее номер напёрстка, под которым находился шарик в самом начале.

В первом примере шарик изначально мог лежать под средним напёрстком и ведущий совершил четыре действия.

1. Первым действием ведущий поменял местами левый и средний напёрстки. В результате шарик оказался под левым напёрстком.

2. Вторым действием ведущий поменял местами средний и правый напёрстки. Шарик остался под левым напёрстком.

3. Третьим действием ведущий снова поменял местами левый и средний напёрстки. В результате шарик снова оказался посередине.

4. Последним четвёртым действием ведущий опять поменял местами средний и правый напёрстки и шарик оказался под правым напёрстком.

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

Решения, верно работающие при \(n \leq 100\,000\) будут набирать не менее 50 баллов.

Множество \(A = \{a_1, a_2, \ldots, a_k\}\) различных натуральных чисел с суммой \(a_1+a_2+\ldots+a_k=n\) называется генератором квадратов, если сумма любых \(k-1\) элементов этого множества является полным квадратом целого числа.

Например, множество \(\{1, 22, 41, 58\}\) является генератором квадратов, так как \(1 + 22 + 41 = 64 = 8^2\), \(1 + 22 + 58 = 81 = 9^2\), \(1 + 41 + 58 = 100 = 10^2\), \(22 + 41 + 58 = 121 = 11^2\).

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

Формат входных данных
На ввод подаются два целых числа \(n\) и \(k\) (\(2 \le n \le 200\,000\), \(2 \le k \le 30\)).

Формат выходных данных
Если искомый генератор квадратов существует, выведите <<YES>> на первой строке, а на второй строке выведите \(k\) натуральных чисел "— искомое множество.

Если генератора квадратов с заданными параметрами не существует, выведите <<NO>>.

 

У Ани есть клетчатый листок бумаги, на котором она нарисовала прямоугольник размером \(m \times n\).

После этого она раскрасила клетки прямоугольника, которые лежат на его границе.

Сколько клеток раскрасила Аня?

Формат входных данных

На первой строке ввода задано целое число \(m\) (\(1 \le m \le 10^8\)).

На второй строке ввода задано целое число \(n\) (\(1 \le n \le 10^8\)).

Формат выходных данных
Выведите одно целое число — сколько клеток раскрасила Аня.

В этой задаче 10 тестов, каждый оценивается независимо в 10 баллов.

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Недавно в Диваново построили огромную шлюзовую систему. Всего было построено \(n\) шлюзов, \(i\)-й из них имеет объем \(v_i\) литров. Изначально все шлюзы пусты. В каждый шлюз ведет труба, при открытии которой в шлюз будет поступать по \(1\) литру воды в секунду. Исходно все трубы закрыты.

Шлюзовая система устроена так, что если доливать воду в \(i\)-й шлюз сверх его объема, она будет моментально моментально переливаться в шлюз с номером \(i + 1\). Если шлюз c номером \(i + 1\) тоже заполнен, вода будет переливаться дальше. Вода из последнего шлюза будет выливаться в озеро.

Для того, чтобы шлюзы начали функционировать, необходимо заполнить каждый из них. Мэра Дивановской области интересует \(q\) независимых запросов. Для каждого запроса предположим, что изначально все шлюзы пусты и все трубы закрыты, затем одновременно открываются несколько труб. Для \(j\)-го запроса мэр хочет знать, какое минимальное число труб надо включить, чтобы не позже чем через \(t_j\) секунд все шлюзы стали заполнены.

Помогите мэру справиться с этой сложной задачей и ответьте на все его запросы!

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — количество шлюзов.

Во второй строке вводятся \(n\) целых чисел \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)) — объемы шлюзов.

В третьей строке вводится одно целое число \(q\) (\(1 \le q \le 200\,000\)) — число запросов.

В следующих \(q\) строках вводится по одному целому числу \(t_i\) (\(1 \le t_j \le 10^9\)) — время, за которое нужно наполнить все шлюзы в \(j\)-м запросе.

Формат выходных данных
Выведите \(q\) чисел, \(j\)-е из них должно быть равно минимальному числу труб, которое нужно открыть, чтобы наполнить все шлюзы за время \(t_j\). Если за это время наполнить всю шлюзы невозможно, выведите \(-1\).

В первом примере \(6\) запросов:

В запросах \(1, 3, 4\) ответ \(-1\). Чтобы заполнить первый шлюз нужно подождать \(4\) секунды, даже если открыты все трубы.

В шестом запросе можно открыть трубы в шлюзах \(1, 3\), и \(4\). Тогда через \(4\) секунды заполнятся шлюзы \(1\) и \(4\). Через \(1\) секунду \(1\) литр воды перельётся в шлюзы \(2\) и \(5\). Шлюз \(3\) будет заполнен своей трубой.

Аналогично во втором запросе можно открыть трубы в шлюзах \(1, 3\) и \(4\).

В пятом запросе можно открыть трубы в шлюзах с номерами \(1, 2, 3, 4\).

У Алексея есть набор, который состоит из n палочек длины 1 и m палочек длины 2. Палочки можно соединять между собой, либо выстраивая их в линию, либо под прямым углом. 

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

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

Формат входных данных
Первая строка входных данных содержит целое число n - количество палочек длины 1 (1 ≤ n ≤ 10⁹). 
Вторая строка входных данных содержит целое число m - количество палочек длины 2 (1 ≤ n ≤ 10⁹).

Формат выходных данных
В единственной строке выведите единственное целое число - максимальную площадь прямоугольника, который можно сложить из имеющихся палочек. Если из имеющихся палочек невозможно сложить никакой прямоугольник, то выведите число 0.

Замечание
В первом примере есть 5 палочек длины 1. Из них можно сложить квадрат со стороной 1, его площадь равна 1, при этом одна палочка останется.
Во втором примере есть 4 палочки длины 1 и 3 палочки длины 2. Из них можно сложить прямоугольник размера  2 x 3.
В третьем примере есть 3 палочки длины 1, из них невозможно сложить прямоугольник.

Пётр любит шахматы и математику. Он знает, что самая мощная фигура в шахматах - это ферзь, потому что он ходит и как ладья, на все клетки на одной с ним вертикали или горизонтали, и как слон, на все клетки по диагоналям. Ферзя можно поставить на доску 8 X 8 так, чтобы он контролировал (то есть мог переместиться в эти клетки за один ход) целых 27 клеток доски!

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

Формат входных данных
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 10⁹) - размер доски по вертикали.
Вторая строка входных данных содержит целое число m (1 ≤ m ≤ 10⁹) - размер доски по горизонтали.
Формат выходных данных

Программа должна вывести одно целое число - максимальное количество клеток, которое может контролировать ферзь на доске n x m.

Обратите внимание на то,  что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

Замечание
Второй пример из условия приведён на рисунке. Крестиками обозначены клетки, которые контролирует ферзь.