Алгоритмы

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

Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито \(n\) сортов, \(i\)-й сорт характеризуется уровнем крепости \(p_i\) и высотой слоя, который он занимает в кружке, \(h_i\). При этом если \(i < j\), то слой кофе \(i\)-го сорта находится ниже кофе \(j\)-го сорта. Также известно, что высота кружки равна \(\sum\limits_{i=1}^n h_i\), то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.

Для разнообразия иногда хочется получить из такого <<коктейля>> напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как \[P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}\]

Чтобы как-то изменять \(P\), можно

1. выбрать трубочку произвольной высоты \(h\);

2. один или более раз выполнить следующее: погрузить ее в напиток на любую глубину от \(0\) до \(h\) включительно относительно верхнего края кружки (не относительно текущего уровня жидкости) и отпить произвольное (не обязательно целое) количество кофе с того уровня, на который попал нижний конец трубочки.

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

Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости \(t_i\), и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка \(t_i\).

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(q\) — количество слоев кофе в кружке и количество запросов (\(1 \le n, q \le 2 \cdot 10^5\)).

Следующие \(n\) строк содержат по два целых числа \(p_i\) и \(h_i\) — уровень крепости и высоту \(i\)-го снизу кружки слоя кофе (\(1 \le p_i, h_i \le 10^9\)). Гарантируется, что сумма \(p_i \cdot h_i\) по всем \(i\) не превосходит \(10^{18}\).

В \(i\)-й из следующих \(q\) строк дано единственное целое число \(t_i\), определяющее \(i\)-й запрос (\(1 \le t_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых содержится единственное целое число от \(0\) до \(n\) — ответ \(i\)-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число \(-1\).

 

Замечание
Для примера из условия:

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

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

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

4. В четвертом запросе невозможно добиться уровня крепости \(4\).

Если вас интересует математика, то эта задача для вас.

Будем называть целое число \(n\) \(k\)-степенным, если его можно разложить в сумму различных степеней числа \(k\), то есть если \(n\) представимо в виде \(n = k^{a_1} + k^{a_2} + \ldots + k^{a_d}\), где все \(a_i\) целые и \(a_i \ne a_j\) для всех \(i \ne j\).

Ответьте на множество запросов: какое минимальное целое число, большее либо равное \(n_i\), является \(k_i\)-степенным?

Формат входных данных
Первая строка ввода содержит целое число \(q\) — количество запросов, на которые вам предстоит ответить (\(1 \le q \le 10^5\)).

Каждая из следующих \(q\) строк содержит два целых числа \(n_i\) и \(k_i\), описывающие \(i\)-й запрос (\(1 \le n_i \le 10^9\); \(2 \le k_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых выведите минимальное \(k_i\)-хорошее число, большее либо равное \(n_i\).

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

В этом году в финал вышли команды <<Капибары>> и <<Бурундучки>>. Петя и Вася очень любят хоккей, но во время турнира они были на сборах по информатике. Теперь они решили просмотреть все матчи финального турнира в записи, скачав их с официального сайта. Зайдя на сайт, они обнаружили, что в этом году финальный турнир ФХЛ состоял из \(k\) матчей. Скачав все видеозаписи, ребята начали их смотреть, но неожиданно поняли, что могут предсказать итог турнира, не досмотрев все матчи. Более того, они заметили, что про некоторые матчи они понимают, кто их выиграет, даже не начав смотреть запись.

Например, пусть \(n = 3\) и \(k = 4\). Петя и Вася сразу могут сделать вывод, что турнир закончится со счетом по матчам \(3:1\) или \(1:3\), ведь всего будет сыграно 4 игры. Пусть первый матч закончился победой команды <<Капибары>>, счет стал \(1:0\), второй матч также закончился победой команды <<Капибары>>, счет стал \(2:0\). Теперь ребята точно знают, что победителем турнира станет команда <<Капибары>>, ведь если бы турнир выиграла команда <<Бурундучки>>, то финальный счет был бы \(2:3\) и всего было бы сыграно 5 игр. Более того, команда <<Бурундучки>> гарантированно выиграет третий матч, иначе окончательный счет был бы \(3:0\), а команда <<Капибары>> "— четвертый матч.

По заданным \(n\), \(k\) и результатам игр определите, после какой игры Петя и Вася поймут, какая команда станет победителем турнира, а также про каждый матч определите, знают ли ребята победителя этого матча до того, как посмотрят его.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 100\), \(n \le k \le 2n-1\)). Вторая строка ввода содержит \(k\) целых чисел: \(i\)-е из них равно 1, если \(i\)-й матч выиграла команда <<Капибары>>, либо 2, если \(i\)-й матч выиграла команда <<Бурундучки>>.

Гарантируется, что по итогам турнира одна из команд выиграла ровно \(n\) матчей, причем ни одна из команд не выигрывает \(n\) матчей до того, как будут сыграны все \(k\) матчей, описанных во входных данных.

Формат выходных данных
Выведите две строки. Первая строка должна содержать одно число \(z\) (\(1 \le z \le k\)) "— номер матча, после которого ребята могут однозначно определить победителя турнира.

Вторая строка должна содержать \(k\) чисел, каждое из которых равно 0 или 1. Выведите 0 для матчей, победитель которых не известен до его просмотра, и 1 для тех матчей, победителя которых ребята могут однозначно предсказать, посмотрев все предыдущие матчи и зная числа \(n\) и \(k\).

У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Для каждой позиции \(i\) и для каждого подотрезка массива \([l, r]\), который содержит позицию \(i\) (то есть, \(1 \le l \le i \le r \le n\)), Вася вычисляет значение \(c_{i, l, r}\) следующим образом. Вася выписывает на листочек числа из массива с позиции \(l\) до позицию \(r\), всего \(len=r-l+1\) чисел (среди которых обязательно есть \(a_i\)), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции \(j\) в полученном отсортированном массиве стоит число \(a_i\). Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции \(mid = \lceil (len+1) / 2 \rceil\) (\(len / 2 + 1\) в случае четного \(len\) и \((len+1)/2\) в случае нечетного \(len\)). Полученное расстояние \(|j - mid|\) и есть искомая величина \(c_{i,l,r}\).

Например, если у Васи был массив \(a=\{5,1,3,2,1,7\}\), а \(i=2\), \(l=2\), \(r=5\), то Вася выпишет на листочек числа \(\{1,3,2,1\}\), отсортирует их и получит массив \(\{1,1,2,3\}\), длина которого равна 4. Середина этого массива находится на позиции \(4/2+1=3\), а искомое число \(a_i=1\) стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение \(c_{2,2,5}\).

Для каждой позиции \(i\) Вася вычисляет величину \(b_i\), которая равна максимуму среди значений \(c_{i,l,r}\) среди всех подотрезков, содержащих позицию \(i\).

Как вы видите, определение числа \(b_i\) достаточно сложное. Помогите Васе вычислить значения \(b_i\) для всех позиций массива.

Формат входных данных
В первой строке входных данных находится одно целое число \(n\) (\(1 \le n \le 200\,000\)) — размер массива Васи.

Во второй строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — элементы массива.

Формат выходных данных
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно \(b_i\).

Разберем подробнее первый пример.

1. Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок \([1,5]\), где \(l=1\) и \(r=5\). Для вычисления \(c_{i,l,r}=c_{1,1,5}\) Вася выпишет числа \(\{5, 4, 3, 2, 1\}\) и после сортировки получит \(\{1, 2, 3, 4, 5\}\). Середина этого массива находится на позиции 3, а искомое число \(a_1=5\) — на позиции 5. Таким образом, \(c_{1,1,5}=2\). Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, \(b_1=2\).

2. \(b_2=c_{2,2,4}\).

3. \(b_3=c_{3,3,5}\).

4. \(b_4=c_{4,1,4}\). Действительно, если выписать числа на подотрезке \([1,4]\), то получится массив \(\{5,4,3,2\}\), который после сортировки превратится в \(\{2,3,4,5\}\). Середина этого массива находится на позиции \(3\), а искомый элемент \(a_4=2\) — на позиции 1. Таким образом, \(c_{4,1,4}=2\).

5. \(b_5=c_{5,1,5}\).

 

Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.

Всего в олимпиаде участвуют \(n\) человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом \(x\) минут. Таким образом первый участник начнёт тур в момент времени \(0\), второй участник начнёт тур в момент времени \(x\), третий — в момент времени \(2 \cdot x\) и так далее.

Несмотря на разное время начала, длительность тура для каждого участника составляет ровно \(t\) минут. Из-за этого некоторые участники заканчивают писать тур раньше остальных. Когда участник заканчивает писать тур, величина недовольства организацией олимпиады для этого участника равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.

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

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

Во второй строке вводится единственное целое число \(x\) (\(1 \le x \le 2 \cdot 10^9\)) — интервал в минутах между временами начала тура для участников.

В третей строке вводится единственное целое число \(t\) (\(1 \le t \le 2 \cdot 10^9\)) — длительность тура.

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

В первом примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(5\). К этому времени второй и третий участники уже начнут писать тур, поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт писать в момент времени \(2\) и закончит в момент времени \(7\). К этому моменту третий и четвёртый участники уже начнут писать тур, поэтому недовольство второго будет равно \(2\).

Третий участник начнёт писать тур в момент времени \(4\) и закончит в момент времени \(9\). К этому времени четвёртый участник уже начнёт писать тур, поэтому недовольство третьего будет равно \(1\).

Четвёртый участник начнёт писать тур в момент времени \(6\) и закончит в момент времени \(11\). В момент времени \(9\) уже никто не будет писать тур, поэтому недовольство четвёртого будет равно \(0\).

Таким образом, суммарное недовольство всех участников будет равно \(2+2+1+0=5\).

Во втором примере первый участник начнёт писать тур в момент времени \(0\) и закончит в момент времени \(2\). К этому моменту второй участник уже будет писать тур, а третий участник как раз начнёт в момент времени \(2\). Поэтому недовольство первого участника будет равно \(2\).

Второй участник начнёт в момент времени \(1\) и закончит в момент времени \(3\). К этому моменту только третий участник будет всё ещё писать тур.

Таким образом, суммарное недовольство всех участников будет равно \(2+1=3\).

Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.

Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).

Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).

Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.

Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).

Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).

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

Известно, что каждый город относится ровно к одной провинции. Город \(v\) относится к провинции \(t_v\). Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер \(1\).

Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить. В городе \(v\) он равен \(c_v\).

Вам приходят запросы двух типов:

1. Изменить провинцию, к которой относится город \(v\), на \(t_{new}\)

2. В \(k\) городах с номерами \(a_1, a_2, \ldots, a_k\) появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции \(t\), после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером \(v\), то они получат \(c_v \cdot num_v\), где \(c_v\) — коэффициент города \(v\), а \(num_v\) это количество караванов, проходящих через этот город.

Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Формат входных данных
В первой строке даны два целых числа \(n\) и \(q\) (\(2 \le n \le 200\,000, 1 \le q \le 200\,000\)) — количество городов и количество запросов.

Во второй строке дано \(n - 1\) целое число \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), где число \(p_i\) означает, что существует дорога между городами \(i\) и \(p_i\).

В третьей строке дано \(n\) целых чисел \(t_1, t_2, \ldots, t_n\) (\(1 \le t_i \le n\)) — номера провинций у городов.

В четвертой строке дано \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^9\)) — коэффициенты успешности грабежа.

Далее идет \(q\) строк описаний запросов. В начале каждой строки дано одно целое число \(x_i\) (\(1 \le x_i \le 2\)) — тип запроса.

1. Если \(x_i = 1\), то далее идет два целых числа \(v\) и \(t_{new}\) (\(1 \le v, t_{new} \le n\)) — номер города, у которого меняется провинция, и номер его новой провинции.

2. Если \(x_i = 2\), то далее идут целые числа \(t\) и \(k\), и \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le t, k, a_i \le n\)) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все \(a_i\) различны. Также гарантируется, что сумма \(k\) по всем запросам второго типа не превышает \(200\,000\).

Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен \(0\).

Примечание
В первом запросе караваны идут из городов с номерами \(3\) и \(4\) и нужно ограбить их в городе из третьей провинции. Это те же самые города с номерами \(3\) и \(4\), через каждый из которых пройдет по одному каравану. Поэтому разбойники ограбят караваны в третьем городе и получат \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

Во втором запросе караваны также идут из городов с номерами \(3\) и \(4\), но теперь нужно ограбить их в городе из первой провинции. В первой провинции находятся города \(1\) и \(2\), через каждый из которых пройдет два каравана. Среди них разбойники выбирают город \(2\), потому что \(c_2 > c_1\) и ответ на этот запрос равен \(c_2 \cdot 2 = 3 \cdot 2 = 6\).

В третьем провинция для города \(3\) изменяется на \(1\).

В четвертом запросе караваны снова идут из городов с номерами \(3\) и \(4\), и нужно ограбить караваны в городе из первой провинции. То есть разбойники могут ограбить караваны в одном из городов с номерами \(1, 2\) или \(3\). Через города с номерами \(1\) и \(2\) пройдет два каравана, а через город \(3\) только один. Разбойникам выгодно ограбить караваны в городе \(3\) и получить \(c_3 \cdot 1 = 10 \cdot 1 = 10\).

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

В качестве первого приза Миша может взять любой приз, а затем Миша может взять приз, если его стоимость строго больше стоимости предыдущего взятого им приза.

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

Формат входных данных
Первая строка ввода содержит целая число \(n\) — количество призов (\(1 \le n \le 1000\)). Вторая строка содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) — стоимости призов в том порядке, в котором их покажут Мише (\(1 \le a_i \le 10^9\)).

Формат выходных данных
Выведите одно число — максимальную суммарную стоимость призов, которые может получить Миша.

Числа Фибоначчи определяются следующим образом: \(F_1 = 1\), \(F_2 = 2\), а для \(n > 2\) выполнено \(F_n = F_{n - 2} + F_{n - 1}\). Таким образом, начало последовательности чисел Фибоначчи выглядит так \(1, 2, 3, 5, 8, 13, 21, \ldots\).

Вам заданы числа \(n\) и \(k\). Требуется найти все способы представить число \(n\) в виде суммы неубывающих чисел Фибоначчи, причем кажое число разрешается использовать не более \(k\) раз.

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

Вторая строка ввода содержит число \(k\) (\(1 \le k \le 20\)).

Формат выходных данных
Выведите все искомые представления, по одному на строке. Разделяйте числа знаком <<+>>, не используйте пробелы.

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

Даша очень любит представлять числа в виде суммы. Сегодня Даша хочет выписать все возможные представления числа \(n\) в виде суммы \(k\) слагаемых.

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

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

Формат входных данных
Первая строка ввода содержит число \(n\) (\(-15\le n \le 15\)).

Вторая строка содержит число \(k\) (\(1 \le k \le 15\)).

Гарантируется, что общее число представлений не превышает \(10^5\).

Формат выходных данных
Выводите представления по одному на строке, перед положительными и нулевыми слагаемыми, кроме первого в представлении, выводите знак плюс. Не выводите пробелы.

Космический аппарат "Звезда" выполняет задачу по фиксации показаний уровня космической радиации. Каждое показание записывается в виде целого числа. В процессе первоначальной обработки данных, для устранения потенциально неточных результатов, убирают из списка K наибольших и K наименьших показаний.
Исходя из списка полученных показаний и количестве исключаемых показаний, определите самое высокое точное показание и целую часть среднего арифметического всех точных показаний.

Формат входных данных
В первой строке записаны два числа через пробел: N – общее количество показаний (натуральное число, не превышающее 10 000) и K – количество исключаемых минимальных и максимальных показаний. В следующих N строках находятся значений каждого показания (все числа натуральные, не превышающие 10000), каждое в отдельной строке.

Формат выходных данных
Запишите в ответе два числа: сначала наибольшего точного показания, а затем целую часть среднего арифметического всех точных показаний.

Целое число \(x\) называется свободным от квадратов, если нет такого целого числа \(y > 1\), что \(x\) делится на \(y^2\), то есть \(x = y^2z\) для некоторого целого \(z\).

Даны числа \(l\) и \(r\). Требуется найти число пар целых чисел \((a, b)\), таких что \(l \le a < b \le r\), и числа \(a\), \(b\), а также их произведение \(ab\) свободны от квадратов.

Формат входных данных
На вход подается две строки, первая содержит целое число \(l\), а вторая "— целое число \(r\) (\(1 \le l < r \le 10^9\), \(r - l \le 1000\)).

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

Примечание
В примере подходят пары \(a = 3, b = 5\), \(a = 5, b = 6\). Число \(4\) не может входить в пару, так как \(4 = 2^2\cdot 1\), а пара \(a = 3, b = 6\) не подходит, так как \(ab = 3\cdot 6 = 18 = 3^2\cdot 2\).

Артур Числовский получил на свой день рождения массив из N целых чисел в подарок. Но ему он не понравился. Артур Числовский хочет сделать этот массив красивым. Числовский считает массив A1, A2, A3 ... AN красивым, если A1 > AN. Чтобы сделать его красивым, Артур Числовский может поменять местами любые два числа в массиве. Кроме того, Артур Числовский может выполнять эту операцию любое количество раз над смежными парами целых чисел в массиве A. Найдите количество способов, которыми Артур Числовский может сделать этот массив красивым. Два способа считаются одинаковыми, если итоговый массив после всех обменов имеет одинаковые значения A1 и AN.
 

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

Первая строка ввода содержит целое число N, обозначающее количество элементов в массиве A. Следующая строка ввода содержит N разделенных пробелом целых чисел, обозначающих A1,A2,A3 ... AN соответственно. 

Ограничения

1 ≤ N ≤ 106
1 ≤ Ai ≤ 106

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

Выведите одно число - количество способов, с помощью которых можно сделать данный массив красивым.


Примечание
В приведенном примере общее количество способов равно (5,1),(4,1),(3,1),(2,1),(5,2),(4,2),(3,2),(5,3),(4,3),(5,4). Первое число в приведенной выше паре - A[1], а второе - A[N]. Заметим, что два способа считаются одинаковыми, если A[1] и A[N] в результирующем массиве после обмена совпадают.

У Кати есть веревочка длиной \(n\) сантиметров.

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

Когда Катя закончила разрезать веревочку, она разложила получившиеся веревочки в порядке невозрастания длины и хочет ответить на \(q\) запросов: какая длина \(t_i\)-й веревочки в получившемся порядке.

Например, пусть \(n=100\) и \(k=5\). Тогда у Кати последовательно есть наборы веревочек следующей длины: \([100]\), \([50, 50]\), \([50, 25, 25]\), \([25, 25, 25, 25]\), \([25, 25, 25, 13, 12]\), \([25, 25, 13, 13, 12, 12]\).

Формат входных данных
На первой строке ввода дано целое число \(n\) (\(2 \le n \le 10^{18}\)).

На второй строке дано целое число \(k\) (\(1 \le k \le n-1\)).

На третьей строке дано целое число \(q\) (\(1 \le q \le k + 1\), \(1 \le q \le 5000\)).

На четвертой строке даны \(q\) целых чисел \(t_1, t_2, \ldots, t_q\) (\(1 \le t_1 < t_2 < \ldots < t_q \le k + 1\)).

Формат выходных данных
Выведите \(q\) чисел, \(i\)-е из выведенных чисел должно быть равно длине \(t_i\)-й по невозрастанию длине веревочки, которая в итоге есть у Кати.

Рассмотрим разбиения целого положительного числа \(n\) в сумму целых положительных чисел. Будем называть разбиение непростым, если слагаемые в нем упорядочены по неубыванию, причем среди слагаемых нет простых чисел.

Например, для \(n=5\) существует два непростых разбиения: \(1+1+1+1+1\) и \(1+4\).

Задано число \(n\). Выведите все его непростые разбиения на слагаемые.

Формат входных данных
На вход подается число \(n\) (\(1 \le n \le 70\)).

Формат выходных данных
Выведите все непростые разбиения \(n\) на слагаемые. Слагаемые разделяйте знаком <<+>>. Не выводите пробелы. Разбиения можно вывести в любом порядке.

Физрук формирует дистанцию для забега школьников на уроке. Согласно требованиям, длина дистанции должна быть от \(L\) до \(R\) метров.

Дистанция пройдет вдоль дорожки в парке около школы. Вдоль дорожки растет \(n\) деревьев, первое дерево находится на расстоянии \(d_1\) метров от начала дорожки, \(i\)-е дерево находится на расстоянии \(d_i\) метров от предыдущего дерева для \(i > 1\). Для удобства физрук хочет, чтобы дистанция начиналась либо в начале дорожки, либо около какого-либо дерева, и заканчивалась также около какого-либо дерева.

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

Помогите физруку выбрать точки начала и конца дистанции.

Формат входных данных
Первая строка ввода содержат два целых числа \(L\) и \(R\) (\(1 \le L \le R \le 3 \cdot 10^{14}\)). Обратите внимание, что для считывания \(L\) и \(R\) необходимо хотя бы 64-битный тип данных (<<long long>> в C++).

Вторая строка ввода содержит целое число \(n\) (\(1 \le n \le 300\,000\)).

Третья строка ввода содержит \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа: \(s\) и \(t\) — расстояние от начала дорожки до начала и конца дистанции, соответственно. Должны выполняться условия: \(0 \le s < t\), \(L \le t - s \le R\), \(s = 0\) или \(s\) совпадает с позицией некоторого дерева, \(t\) совпадает с позицией некоторого дерева.

Если выбрать организовать дистанцию не получится, выведите \(s = -1\), \(t = -1\).