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

В 2222 году экспедиция на планету XZ-238 в звездной системе ню Малой Медведицы обнаружила в одной из пещер загадочное устройство. Вдоль стены по прямой расположены n треугольных и n круглых гнезд. Расшифровка инструкций, расположенных рядом на стене, показала, что эти гнезда следует соединить проводами: каждое треугольное гнездо должно быть соединено с каким-либо круглым, расположенным правее.

Были изготовлены n треугольных и n круглых штекеров, которые можно соединять проводами. Однако никакой маркировки нет, поэтому понять какое гнездо следует соединить с каким не удается. Начальник экспедиции хочет заказать с Земли провода. Решено было заказать один большой моток кабеля, который затем нарезать на соединительные провода. Поскольку доставка грузов с Земли дорога, необходимо заказать как можно меньше кабеля. С другой стороны, поскольку неизвестно какое гнездо требуется соединить с каким, нужно заказать такое количество кабеля, чтобы при любом способе соединения длины кабеля хватило на изготовление соединительных проводов. Помогите руководству экспедиции по заданному расположению гнезд вычислить, кабель какой длины следует заказать. Гарантируется, что хотя бы один способ соединить гнезда описанным образом существует.

Например, рассмотрим расположение гнезд, изображенное на рисунке.



Можно соединить треугольное гнездо 1 с круглым гнездом A, а треугольное гнездо 2 − с круглым гнездом B. Для такого соединения необходимы провода длины 5 и 4, суммарная длина − 9. Можно также соединить 1 с B и 2 с A, в этом случае необходимы провода длины 7 и 2, суммарная длина также 9. Таким образом необходимо заказать с Земли кабель длиной 9 метров.

В случае же, показанном на следующем рисунке, есть лишь один способ соединить гнезда: 1 с A, а 2 с B. Гнездо 2 нельзя соединить с A, поскольку A расположено левее. Так что в этом случае необходимо 2 метра кабеля.



Входные данные
Первая строка входного файла содержит число n (1≤n≤1000). Вторая строка содержит n целых чисел, i-е число означает расстояние от начала стены до i-го треугольного гнезда. Третья строка также содержит n целых чисел, i-е число означает расстояние от начала стены до i
-го круглого гнезда. Все числа во второй и третьей строках различны и лежат в диапазоне от 0 до 10⁵.

Выходные данные
Выведите одно число − кабель какой длины необходимо заказать с Земли.

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

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

Вводятся два натуральных числа N (высота доски) и M (ширина доски), не превышающие 100.

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

Выведите последовательность ходов в одном из возможных кратчайших путей. Каждый ход обозначается заглавной латинской буквой:
   U – вверх,
   R – вправо,
   D – вверх и вправо.
Буквы выводятся без пробелов в одной строке.

Какую наибольшую площадь может иметь прямоугольник периметра P, нарисованный на клетчатой бумаге по линиям сетки (сторона клетки равна 1)?

Входные данные
Вводится одно четное натуральное число P (4 ≤ P ≤ 600).

Выходные данные
Выведите одно число – наибольшую возможную площадь.

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

Обычно определяют время выполнения алгоритма по отношению к n - "размеру" входных данных. Это может быть число объектов, которые нужно отсортировать, число точек многоугольника и т.п. Поскольку определение формулы зависимости временной сложности алгоритма от n - непростая задача, было бы замечательно, если бы её можно было автоматизировать. К сожалению, в общем случае это невозможно. Но в этой задаче мы будем рассматривать программы очень простой природы, над которыми это можно проделать. Рассматриваемые программы записаны согласно следующим правилам БНФ, где <число> может быть любым неотрицательным целым числом:

• <Программа> ::= "BEGIN" <Список операторов> "END"
• <Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
• <Оператор> ::= <Оператор LOOP> | <Оператор OP>
• <Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
• <Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
• <Оператор OP> ::= "OP" <число>

Время выполнения такой программы может быть вычислено следующим образом: выполнение оператора OP требует столько единиц времени, сколько указано в его параметре. Список операторов, заключённый в оператор LOOP, выполняется столько раз, сколько указано в параметре оператора, то есть или заданное константное число раз, если задано число, или n раз, если параметром является n. Время выполнения списка операторов равно сумме времени выполнения его частей. Таким образом, время выполнения программы в целом зависит от n.

Входные данные
В первой строке находится целое число k - число программ во входном файле. Затем идут k программ, удовлетворяющих приведённой грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах BEGIN, END, LOOP и OP, нет их и в целых числах.

Выходные данные
Для каждой программы сначала идёт строка с номером программы. В следующей строке записывается время работы программы в терминах n - многочлен степени не более 10. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое с большей степенью должно предшествовать слагаемому с меньшей степенью, слагаемые с коэффициентом 0 не записываются, множители 1 не записываются. Общий вид второй строки "Runtime = a*n^10+b*n^9+...+i*n^2+j*n+k". Если время выполнения нулевое, нужно вывести "Runtime = 0". За строкой с многочленом должна следовать пустая строка.

Ограничения: вложенность операторов LOOP не превышает 10, размер входного файла не более 2 Кбайт, коэффициенты многочлена в ответе не превышают 50 000.

{F_k} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k - 1 + F_k - 2 (для любого целого k). Даны i, F_i, j, F_j, n (i <> j). Найти F_n. Пример части последовательности:

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x₁ y₁ и x₂ y₂. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.

Ограничения: 1 <= x₁, y₁, x₂, y₂ <= 100, 0 <= D_x < x₁, 0 <= D_y < y₁, все числа целые.

Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, D_x, D_y, разделённые пробелами.

Выходные данные
В первой строке вывести N - количество получившихся площадей, в следующих N строках - сами площади.

Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H₁ = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (H_i = (H_i - 1 + H_i + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = H_N) при условии, что ни одна из лампочек не должна лежать на земле (H_i > 0 для 1 <= i <= N).

Ограничения: 3 <= N <= 1000 - целое, 10 <= A <= 1000 - вещественное.

Входные данные
В первой строке находятся два числа, N и A.

Выходные данные
Вывести одно вещественное число B с двумя знаками после запятой.

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить k
 досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

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

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

Входные данные
Первая строка содержит количество досок в заборе n (1 ≤ n ≤ 10⁹) и вместимость ведерка k (1 ≤ k ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора m (1 ≤ m ≤ 50).
Далее следуют m строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей li и правой границей ri (1 ≤ l_i ≤ r_i ≤ n). Такое описание означает, что не покрашены l_i-я, (l_i+1)-я, …, (r_i–1)-я, r_i-я доски забора (доски нумеруются от 1 до n). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

Недавно Петя научился считать. Он тут же заметил, что число 2 обладает замечательным свойством - 2 + 2 = 2 × 2. Его старший брат Ваня тут же объяснил ему, что дело не в двойке.

"Дело в том, что последовательность 2, 2 - волшебная," - сказал Пете Ваня. - "Волшебная последовательность - это такая последовательность натуральных чисел, что сумма ее членов равна их произведению. Например последовательность 1, 2, 3 - тоже волшебная."

Петя тут же сложил 1, 2 и 3, потом перемножил их и обрадовался.

Теперь Петя хочет найти более длинные волшебные последовательности. Помогите ему!

Входные данные
В первой строке входных данных содержится целое число N (2 <= N <= 100).

Выходные данные
Выведите любую волшебную последовательность длины N. Разделяйте числа пробелами. Члены последовательности не должны превышать 10⁹. Если такой волшебной последовательности длины N не существует, выведите единственное число - "-1".

Помогите Коле решить уравнение Уравнение. a / x²+ b / x + c = 0

Входные данные
Вводятся три числа a, b, c, разделенные пробелами. Все числа целые и по модулю не превосходят 100.

Выходные данные
Требуется вывести все различные корни уравнения (по одному разу в любом порядке). Выведенные корни должны отличаться от точного ответа не более, чем на 0,01. Если уравнение не имеет корней, вывести No solution.

Если уравнение имеет больше 10 корней, вывести Many solutions.

Возьмем кубик и приклеим к его граням еще по такому же кубику. В результате получим фигуру, представленную на втором рисунке. К свободным граням полученной фигуры, приклеим еще кубики. На рисунке представлены "кубооктаэдры" степеней 0, 1, 2.

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

Входные данные
Содержит единственное число - степень кубооктаэдра 0 <= N <= 100000

Выходные данные
Вывести одно число - количество кубиков для кубооктаэдра степени N.

Решить в целых числах уравнение ( ax + b ) : ( cx + d ) = 0.

Входные данные
Вводятся 4 числа: a, b, c и d; c и d не равны нулю одновременно.

Выходные данные
Необходимо вывести все целочисленные решения, если их число конечно, “NO” (без кавычек), если целочисленных решений нет, и “INF” (без кавычек), если их бесконечно много.

В знаменитом магазине <<Двоечка>> продукты продаются всего два дня в неделю — понедельник и вторник — причём в разные дни по разным ценам. Вы захотели купить \(n\) килограммов картофеля на неделю. По понедельникам один килограмм картофеля стоит \(a\) рублей, а по вторникам — \(b\) рублей. Чтобы упростить работу кассирам, в <<Двоечке>> можно покупать только целое число килограммов.

Вам крупно повезло, ведь в <<Двоечке>> проходит акция: каждый понедельник за каждые \(m\) килограммов купленного картофеля дарят ещё один!

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

Формат входных данных
В первой строке вводится целое число \(a\) \((1 \leqslant a \leqslant 10^9)\) — цена одного килограмма картофеля в понедельник.

Во второй строке вводится целое число \(b\) \((1 \leqslant b \leqslant 10^9)\) — цена одного килограмма картофеля во вторник.

В третьей строке вводится целое число \(n\) \((\mathbf{1 \leqslant n \leqslant 10^6})\) — желаемое количество килограммов картофеля.

В четвертой строке вводится целое число \(m\) \((1 \leqslant m \leqslant 10^6)\) — количество килограммов картофеля, участвующее в акции.

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

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

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

Во втором примере выгодно купить три килограмма в понедельник и получить один килограмм в подарок.

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

В четвертом примере выгодно купить шесть килограммов в понедельник, получить по акции три килограмма и купить еще один килограмм во вторник.

В знаменитом магазине <<Двоечка>> продукты продаются всего два дня в неделю — понедельник и вторник — причём в разные дни по разным ценам. Вы захотели купить \(n\) килограммов картофеля на неделю. По понедельникам один килограмм картофеля стоит \(a\) рублей, а по вторникам — \(b\) рублей. Чтобы упростить работу кассирам, в <<Двоечке>> можно покупать только целое число килограммов.

Вам крупно повезло, ведь в <<Двоечке>> проходит акция: каждый понедельник за каждые \(m\) килограммов купленного картофеля дарят ещё один!

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

Формат входных данных
В первой строке вводится целое число \(a\) \((1 \leqslant a \leqslant 10^9)\) — цена одного килограмма картофеля в понедельник.

Во второй строке вводится целое число \(b\) \((1 \leqslant b \leqslant 10^9)\) — цена одного килограмма картофеля во вторник.

В третьей строке вводится целое число \(n\) \((1 \leqslant n \leqslant 10^9)\) — желаемое количество килограммов картофеля.

В четвертой строке вводится целое число \(m\) \((1 \leqslant m \leqslant 10^9)\) — количество килограммов картофеля, участвующее в акции.

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

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

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

Во втором примере выгодно купить три килограмма в понедельник и получить один килограмм в подарок.

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

В четвертом примере выгодно купить шесть килограммов в понедельник, получить по акции три килограмма и купить еще один килограмм во вторник.

Для МОШ по информатике было придумано и подготовлено \(n\) задач. Всего в олимпиаде будут учавствовать \(k\) школьников. И вот до олимпиады осталась всего неделя! Но, как вы знаете, некий <<Турист>> очень любит придумывать задачи и потом давать их на разные олимпиады. А так как <<Турист>> ну уж очень умный, то он явно придумает и даст все задачи, которые придумало жюри МОШа. В рамках подготовки к олимпиаде, школьники будет решать задачи <<Туриста>>. Причём вы знаете, что каждый из участников прорешает за неделю не менее \(a\) и не более \(b\) задач из тех, что собираются дать на МОШ. Жюри даст на олимпиаду все задачи, которые не решал никто из участников ранее. Скажите минимальное и максимальное количество задач, которые могут быть даны на МОШ из заранее подготовленных.

Формат входных данных
В первой строке вводится число \(n\) \((1 \leqslant n \leqslant 10^9)\) — количество задач, подготовленных для МОШ по информатике.

Во второй строке вводится число \(k\) \((1 \leqslant k \leqslant 10^9)\) — число участников МОШ.

В третьей строке вводится число \(a\) \((1 \leqslant a \leqslant n)\) — минимальное число задач, которое прорешает каждый из участников в течение недели.

В третьей строке вводится число \(b\) \((a \leqslant b \leqslant n)\) — максимальное число задач, которое может прорешать каждый из участников в течение недели.

Формат выходных данных
Выведите два числа – минимальное и максимальное число задач, которые жюри может дать на МОШ.

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

Незаметно для друга Алиса узнала, что ему большего всего нравятся \(k\) различных цветов. Алиса приняла решение связать шарф размером \(n \times m\), в котором будут чередоваться полоски различных цветов. Её друг никогда не ищет легких путей, поэтому она решила, что шарф с горизонтальными или вертикальными полосками покажется ему слишком <<примитивным>>. Алиса решила, что полоски определённо должны быть диагональными!

Закончив вязать шарф, Алиса вспомнила, что один из \(k\) цветов её друг считает особенным! Это цвет \(c\), который по его мнению приносит школьникам удачу на олимпиадах по информатике. И Алисе стало невероятно интересно, сколько фрагментов шарфа имеют именно такой цвет. Шарф получился очень большим, Алиса очень устала, пока его вязала, поэтому сама она уже не может ответить на этот вопрос и просит вас о помощи...

Более формально шарф можно представить в виде таблицы размером \(n \times m\), каждая клетка которой покрашена в один из \(k\) цветов. Цвета нумеруются от \(1\) до \(k\).

Первая строка таблицы покрашена в цвета \(1\), \(2\), ..., \(k\), \(1\), \(2\), ..., \(k\) и т.д. Каждая следующая строка получена из предыдущей сдвигом влево на одну клетку. Таким образом, таблица состоит из диагональных полос.

При \(n = 4\), \(m = 8\) и \(k = 3\) таблица будет иметь следующий вид:

По данным числам \(n\), \(m\), \(k\) и \(c\) определите, сколько всего клеток покрашено в цвет \(c\).

Формат входных данных
Первая строка входных данных содержит натуральное число \(n\) — ширину шарфа.

Вторая строка входных данных содержит натуральное число \(m\) — длину шарфа.

Третья строка входных данных содержит натуральное число \(k\) — количество любимых цветов друга Алисы.

Числа \(n\), \(m\) и \(k\) не превосходят \(10^9\).

Четвёртая строка входных данных содержит натуральное число \(c\) — номер особенного цвета (\(1\le c \le k\)).

Формат выходных данных
Программа должна вывести одно целое число — количество клеток шарфа, которые покрашены в цвет \(c\).

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

Замечание

Картинка соответствует примеру из условия. Шарф имеет размеры \(4\times8\) и состоит из клеток трёх цветов. В цвет \(1\) покрашены \(11\) клеток.

Поле в игре <<Речной бой>> представляет собой полоску длины \(n\) клеток и шириной в одну клетку. Где-то на поле расположен корабль из \(k\) клеток (\(k \le n\)). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: <<мимо>>, <<ранен>> или <<убит>>.

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

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

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

Замечание

В первом примере поле состоит из \(n=4\) клеток, корабль имеет длину \(k=2\). Первый выстрел нужно сделать в одну из двух центральных клеток. Если результатом будет <<ранен>>, то вторая клетка корабля находится в одной из двух соседних клеток, и за два выстрела мы гарантированно потопим корабль Если результатом первого выстрела будет <<мимо>>, то корабль занимает две единственные свободные смежные клетки, которые тоже можно подбить двумя выстрелами. Итого нужно 3 выстрела. Двух выстрелов недостаточно, так как всегда есть шанс промахнуться первым выстрелом.

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

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

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

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

Выведите единственное число — количество упаковок, которое должна купить Алиса.

Замечание

В первом примере Алиса купит две упаковки с конфетами. В первой упаковке лежат 2 конфеты одного вида, и 1 конфета другого вида. Если вторая упаковка будет такая же, как и первая, то у Алисы окажется 4 конфеты одного вида и 2 конфеты другого вида. Если вторая упаковка будет отличаться от первой, то у Алисы будет по 3 конфеты каждого вида. В любом случае у Алисы найдётся 3 конфеты одного вида.

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

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

Дети с интересом восприняли идею и вырезали из бумаги \(a\) звездочек и \(b\) снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте \(x\) звездочек и \(y\) снежинок, где \(0 \le x \le a\) и \(0 \le y \le b\). Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие \(x + y > 0\).

Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты \(n\) оленей, поэтому если будут отправлены \(x\) звездочек и \(y\) снежинок, величина \(x+y\) должна делиться на \(n\).

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

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

В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число \(t\) — количество тестов (\(1 \le t \le 10^5\)).

Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел \(n\), \(a\) и \(b\) — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (\(4 \le n \le 10^9\); \(0 \le a, b \le 10^9\)).

Формат выходных данных
Выведите \(t\) чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

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

Во втором тесте у Санты также \(4\) оленя, но дети вырезали \(4\) звездочки и \(4\) снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.

На сегодняшнем уроке ИЗО весь класс рисует зимний лес. К сожалению, с передачей художественных образов изобразительными методами дела у Тимофея обстоят из рук вон плохо. Но хоть что-то нарисовать нужно, поэтому Тимофей рисует елочки по клеточкам.

Каждая елочка имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями, находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите елки кисти Тимофея красотой от 0 до 5 включительно.

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

Входные данные

Программа получает на вход одно целое число n — красоту ёлки (0 ≤ n ≤ 2×10⁹).

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

Выходные данные

Программа должна вывести одно целое число — площадь елки красоты n.