Дан трёхмерный массив. Найдите сумму на параллелепипеде со сторонами, паралельными осям координат.

Много в мире разных часовых поясов! Именно поэтому соревнования по программированию часто бывают в неудобное для некоторых людей время. Как-то раз Гриша и Егор решили поучавствовать в соревновании, которое заканчивалось очень поздно. Именно поэтому ребята решили переночевать в гостинице, чтобы не возвращаться домой поздно. Однако все не так просто. Родители Егора и Гриши очень волнуются за своих детей, поэтому они решили установить по всему городу камеры, чтобы видеть, где находятся ребята.

В городе, где живут программисты 1 ≤ n ≤ 500 000 перекрестков, соединенных n - 1 дорогой так, что между любыми двумя перекрестками существует путь по дорогам.

Родители собираются установить на перекрестках города камеры, радиус действия которых равен длине дороги. Родители будут спокойны, если смогут видеть ребят на любой дороге и на любом про перекрестке. Иными словами, для каждого перекрестка должен существовать перекресток, находящийся на расстоянии не более одной дороги, такой что на нем установлена камера и для любой дороги должна быть установлена камера хотя бы на одном конце этой дороги. Установка камер  — затратное дело, поэтому для каждого перекрестка с номером i известна стоимость 1 ≤ cost _i ≤ 10 ⁹ установки камеры на нем.

Помогите родителям установить камеры надлежащим образом за минимальную стоимость.

В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c _i , время его завоза в магазин a _i и время его вывоза из магазина b _i .

У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m _j , время s _j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k _j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k _j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.

Помогите Иннокентию определить, какие из его планов можно выполнить.

Аркадий и Алексей придумали новую игру. Листок клетчатой бумаги размером 2 ^N ×2 ^M клеток заполняется цифрами (по одной цифре в каждую клетку). Затем начинается собственно игра: тот, чья очередь ходить, разрезает листок пополам вдоль короткой стороны (или любой стороны, если листок квадратный), выбирает любую из половин и выбрасывает ее; оставшаяся половина передается другому игроку. При этом игрок получает очки за каждую пару клеток, бывших соседними до разрезания:

• если в соседних клетках были одинаковые цифры, то игрок получает 3 очка;

• если в соседних клетках были цифры одинаковой четности, то игрок получает 1 очко;

• если в соседних клетках были цифры разной четности, то игрок получает 0 очков.

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

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V _i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.

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

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.