Тимофей, справившись с контрольной работой, задумчиво рисует на клетчатом листочке орнамент в форме пазла. Отдельный кусочек-паттерн представляет собой квадрат 3 × 3, по четырём сторонам которого могут быть вырезаны или добавлены квадратики 1 × 1 (но только если эти стороны не являются наружными для общей прямоугольной фигуры). По размерам фигуры определите длину всех проведённых мальчиком линий.
Формат входных данных
Две строки входных данных содержат два натуральных числа n и m — количество кусочков-паттернов по вертикали и горизонтали.
Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например longlong в C++, int64 в FreePascal, long в Java.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
1 ≤ n, m ≤ 108
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при m = 1, получат не менее 20 баллов.
Решения, верно работающие при m = 2, получат не менее 20 баллов.
Пояснение к примерам
В первом примере дан тривиальный пазл размером 1 × 1 паттерн. Длина всех линий соответствует периметру квадрата 3 × 3 и равна 12.
Во втором примере дан пазл размером 2 × 1 паттерн. Длина всех линий равна периметру прямоугольника 6 × 3 и внутренней ломаной длины 5.
Вокруг стола пустили пакет с семечками. Первый взял 1 семечку, второй — 2, третий — 3 и так далее: каждый следующий брал на одну семечку больше. Известно, что на втором круге было взято в сумме на s семечек больше, чем на первом. Сколько человек сидело за столом?
Формат входных данных
Единственная строка входных данных содержит натуральное число s. Гарантируется корректность s.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Ограничения
1 ≤ s ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при s ≤ 105, получат не менее 40 баллов.
Пояснение к примеру
В примере за столом сидело 2 человека. Первый взял 1 семечку, второй — 2. Потом первый взял 3 семечки, второй — 4. Итого на втором круге взято 7 семечек, на первом — 3 семечки. Разность соответствует входным данным.
В Научно-исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня заведующий отделом для проверки одной из гипотез дал Тимофею следующее задание: определить, сколько есть способов выбрать из первых n натуральных чисел два различных числа так, чтобы их сумма являлась квадратом некоторого натурального числа?
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
1 ≤ n ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n ≤ 100, получат не менее 20 баллов.
Решения, верно работающие при n ≤ 1000, получат не менее 40 баллов.
Пояснение к примеру
В примере дано n = 10. Переберем все возможные пары чисел из диапазона от 1 до 10 и сложим их — в семи случаях получим квадрат.
Всадник — это фигура в сказочных шахматах, которая перемещается на неограниченное расстояние в одном направлении при условии, что на её пути нет фигур. Если препятствием является дружественная фигура, она блокирует дальнейшее движение, а если препятствием является вражеская фигура, её можно захватить, но нельзя перепрыгнуть. В традиционных шахматах три таких всадника: ладья — (0,1)-всадник; слон — (1,1)-всадник; а ферзь сочетает в себе обе возможности.
Один из самых популярных всадников в сказочных шахматах — ночной всадник (1,2), который может совершать неограниченное количество ходов конём в любом направлении (как и другие всадники, он не может менять направление на полпути во время своего хода). На диаграммах обозначается перевернутой фигуркой коня.
На шахматной доске размером n × m, на поле с координатами x, y расположен одинокий ночной всадник. Определите, на какое количество полей эта фигура может переместиться за один ход?
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m. Во второй строке в том же формате содержатся координаты ночного всадника x и y.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи.
Ограничения
1 ≤ x ≤ n ≤ 1018
1 ≤ y ≤ m ≤ 1018
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n, m ≤ 10, получат не менее 40 баллов.
Решения, верно работающие при n, m ≤ 105, получат не менее 60 баллов.
Песенный конкурс «Невровидение» — знаменитый конкурс эстрадной песни среди стран континента Невропа. В конкурсе участвует по одному представителю от каждой из стран, которые подали заявки на участие. После выступления всех участников наиболее популярная песня определяется путём голосования жюри, в котором участвуют все страны.
В этом году в конкурсе впервые принимают участие все n стран континента. Жюри каждой страны выбирает не более k наиболее понравившихся исполнителей (исключая участника из своей страны) и присваивает им баллы от 1 до k. После этого баллы всех жюри складываются и определяется победитель, набравший наибольшее количество баллов (или несколько, если высший балл набрали более одного участника).
По результатам голосования жюри определите победителя конкурса.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и k. В следующих n строках через пробел расположены k + 1 названия стран, первое из которых — название страны, которая голосует, остальные — названия стран, получившие баллы от жюри этой страны. Все названия стран указаны в виде сокращений из 3 заглавных букв английского алфавита. Участники конкурса от этих стран получают баллы от 1 до k в перечисленном порядке. Гарантируется, что голосование проводится корректно.
Формат выходных данных
Выведите в первой строке одно натуральное число p — количество победителей конкурса. В следующей строке в лексикографическом порядке через пробел выведите названия стран-победителей конкурса. В последней строке выведите одно натуральное число b — набранное победителем количество баллов.
Ограничения
1 ≤ k < n ≤ 50
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере дано четыре страны-участницы конкурса. Жюри каждой страны голосует за две наиболее понравившиеся композиции.
Жюри первой страны ABC присудило 1 балл участнику из страны HOL и 2 балла участнику из страны XYZ.
Жюри второй страны XYZ присудило 1 балл участнику из страны SAP и 2 балла участнику из страны ABC.
Жюри третьей страны SAP присудило 1 балл участнику из страны ABC и 2 балла участнику из страны HOL.
Жюри четвертой страны HOL присудило 1 балл участнику из страны ABC и 2 балла участнику из страны XYZ.
Примеры тестов
№
Стандартный вход
Стандартный выход
1
4 2
ABC HOL XYZ
XYZ SAP ABC
SAP ABC HOL
HOL ABC XYZ
