Квадраты на доске: сколько площади останется

В кабинете математики на квадратной доске нарисовали большой квадрат со стороной a см.

Потом дежурный делает «красивую штуку»: соединяет середины всех четырёх сторон — получается новый квадрат внутри. На следующем шаге он снова соединяет середины сторон уже нового квадрата, и так далее. Всего он сделал это n раз.

Нужно узнать, какая целая площадь (в см²) у квадрата, получившегося после n шагов. Если площадь не целая, выведите её целую часть (то есть ⌊S⌋).

Важно: уже при a до 1 000 000 площадь a² может не влезать в 32-битный тип, как на олимпиадах (используйте 64-битные целые; в Python это не проблема).

Формат ввода

В одной строке два целых числа a и n.

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

Выведите одно целое число — ⌊S⌋, где S — площадь квадрата после n шагов.

Ограничения

• 1 ≤ a ≤ 1 000 000
• 1 ≤ n ≤ 1 000 000
• Время: 1 секунда, память: 256 МБ

Пример

Ввод:

10 1

Вывод:

50

Ключевое наблюдение: если соединить середины сторон квадрата, получится новый квадрат, повернутый на 45°. Его диагональ равна стороне старого квадрата. А площадь квадрата через диагональ: S = d*d / 2. Значит при стороне a новая площадь равна a*a/2, то есть ровно в 2 раза меньше.

Дальше всё повторяется: на каждом шаге площадь делится на 2, поэтому после n шагов: S = a*a / 2^n. Нужно вывести floor(S).

Почему работает приём: мы свели геометрию к простой геометрической прогрессии (умножение на 1/2), а деление на 2^n для неотрицательных целых удобно делать целочисленно.

План решения:

• Посчитайте начальную площадь s = a*a (в Python не переполнится; в других языках нужен 64-bit).
• Ответ — floor(s / 2^n).
• Чтобы не использовать вещественные числа и не строить гигантское 2^n, делите степенью двойки битовым сдвигом: ans = s >> n.
• Выведите ans.

Сложность: по сути O(1) по числу шагов (нет цикла по n); сдвиг работает быстро.

Частая ошибка: считать через float (a*a / (2**n)) — при больших n появляются потери точности. Ещё одна ловушка — делать 1 << n при n = 10^6: это создаёт огромный объект; сдвиг s >> n этого не требует.