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

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

Вам дана структура министерства. Каждый работник имеет одного начальника и не более трёх подчинённых(возможно ноль). Единственным исключением является министр  — у него нет начальника(но так же не более трех подчинённых). Конечно нет определённого порядка, в котором перечисляются подчинённые. Департамент состоит из должностного лица, всех его подчинённых и их подчинённых, и т.д.

Есть два особых случая:

• Департамент, в котором должностное лицо  — сам министр, тогда этот департамент есть всё министерство.

• Департамент, в котором у должностного лица нет ни одного подчинённого.

Высотой департамента назовем длину максимальной последовательность сотрудников x ₁ , ..., x _d такую, что сотрудник x _i является начальником сотрудника x _{i + 1} для всех 1 ≤ i < d . Заметим что высота департамента, состоящего из одного сотрудника равна 1 .

Два департамента A и B совпадают, если существует взаимно-однозначное отображение, сопоставляющее каждому сотруднику x _A из департамента A сотрудника x _B из департамента B , таким образом, что сотрудник x _A является начальником сотрудником y _A , тогда и только тогда, когда x _B является начальником y _B . Заметим, что если два департамента совпадают, то они имеют одинаковую высоту, одинаковое количество сотрудников и начальнику первого департамента соответствует начальник второго.

На приведенных картинках департаменты A и B совпадают, а C не совпадает ни с A , ни c B .

Вам необходимо для каждой высоты вычислить количество различных департаментов имеющих такую глубину. Формально требуется построить последовательность n ₁ , ..., n _d , где d это высота всего министерства, а n _i — количество различных департаментов высоты i .

Глобальное потепление — это важная проблема, и Джонни знает об этом. Он решил проанализировать историю температур и найти подпоследовательной дней (не обязательно последовательных), в которой температура строго возрастает. Это убедит неверующих!

Джонни нашёл исторические данные за \(n\) последовательных дней. Температура в \(i\)-й день была \(t_i\).

Формально, нам интересно найти длину наибольшей возрастающей подпоследовательности (НВП) последовательности \((t_1, t_2, \ldots, t_n)\), то есть наибольшее такое \(k\), что возможно выбрать возрастающую последовательность индексов \(1 \leq a_1 lt a_2 \lt \ldots \lt a_k \leq n\), для которой \(t_{a_1} \lt t_{a_2} \lt \ldots \lt t_{a_k}\).

Джонни хочет найти действительно длинную подпоследовательность, а поэтому он решил сжульничать. Сначала он выберет непустой отрезок дней и целое число \(d\) (\(-x \leq d \leq x\)), а затем увеличит температуру в каждый из этих дней на \(d\). Такое небольшое изменение, вероятно, не будет обнаружено обществом, но при этом оно может сделать длину НВП больше. Разрешено выбирать \(d = 0\).

Какая максимально возможная длина НВП после такого изменения?

Обратите внимание на нестандартное ограничение по памяти.

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

Есть много типов игр. Вы интересуетесь в одном из них: Битлото. Выбор был прост, так как это самый простой из предлагаемых типов игр: каждый день случайно выпадает ровно одно число. Вы записываете эти числа за \(n\) последовательных дней и получаете последовательность \(a_1, a_2, \ldots, a_n\). Вы уверены, что в этой последовательности есть какая-то закономерность, а именно, в отрезках из \(l\) последовательных дней. Ваша семья всё ещё не верит вам, так что единственный способ убедить их — это использовать серьёзную математику.

Есть \(n - l + 1\) отрезок дней длины \(l\). \(i\)-й отрезок начинается в позиции \(i\) и содержит элементы \(a_i, a_{i + 1}, \ldots, a_{i + l - 1}\). Расстояние между двумя отрезками — это количество несовпадающих элементов на соответствующих позициях. Другими словами, для отрезков \(x\) и \(y\) это количество таких \(i\) (\(0 \leq i < l\)), что \(a_{x + i}\) и \(a_{y + i}\) различны. И наконец, будем говорить, что два отрезка \(k\)-похожи, если расстояние между ними не превосходит \(k\).

Зафиксированы последовательность и число \(l\). Вам даны \(q\) запросов. В каждом запросе вам дано число \(k_j\) и для каждого из \(n - l + 1\) отрезов вы должны найти количество отрезков той же длины, которые \(k\)-похожи на данный (не считая сам этот отрезок).

Джонни основывает Bytecomp — компанию, которая предлагает вычислительные мощности в облаке. Компании этого профиля обычно обладают большим количеством быстрых компьютеров, на которых производятся вычислениях их клиентов.

Джонни ещё не купил ни одного компьютера. Он пошёл в компьютерный магазин и получил список из \(n\) доступных компьютеров. Каждый компьютер характеризуется колиеством процессорных ядер \(c_i\), частотой \(f_i\) и ценой \(v_i\). Такой компьютер имеет \(c_i\) независимых ядер, не мешающих друг другу, поэтому они могут быть назначены для выполнения разных задач.

Когда клиент делает заказ на ресурс, он определяет требуемое количество ядер \(C_j\) и минимальную необходимую частоту \(F_j\). Также заказ содержит цену \(V_j\), которую клиент собирается заплатить. Если заказ принимается, Bytecomp должна предоставить эксклюзивный доступ к вычислительным мощностям, требуемым клиентом. Джонни должен выбрать \(C_j\) ядер (возможно, из разных компьютеров), каждое частотой хотя бы \(F_j\). Эти ядра не могут быть назначены какому-нибудь другому заказу.

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