Известный программист пробует себя в роли иллюзиониста. Его коронный фокус состоит в следующем.

Для заданного массива из n целых неотрицательных чисел a₁, a₂, ..., a_n он быстро подбирает магическое число b. Целое неотрицательное число b называется магическим для массива, если применение операции побитового исключающего ИЛИ с этим числом к каждому элементу массива превращает его в отсортированный массив. Иначе говоря,

где \(\oplus\) — операция побитового исключающего ИЛИ.

Чтобы фокус был более эффектным, после предъявления магического числа для заданного массива иллюзионист q раз выполняет следующее действие. Он предлагает зрителям изменить один из элементов массива и после этого снова пытается предъявить магическое число. При этом программист настолько отточил свое мастерство иллюзиониста, что каждый раз предъявляет зрителям минимальное возможное магическое число. Иногда фокус не удаётся, так как для полученного массива невозможно подобрать магическое число.

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

Компания тестирует технологию получения антивещества, используемого в качестве топлива в межпланетном звездолёте. Антивещество получается в результате специальных экспериментов в реакторе.

Известно n типов экспериментов, приводящих к получению антивещества. В результате проведения эксперимента i-го типа в выходной контейнер реактора добавляется от l_i до r_i граммов антивещества. Из соображений безопасности запрещается накапливать в контейнере более a граммов антивещества.

Затраты на проведение эксперимента i-го типа составляют c_i, а стоимость одного грамма полученного антивещества составляет 10⁹.

Если после проведения экспериментов в контейнере образовалось t граммов антивещества, а суммарные затраты на проведение экспериментов в реакторе составили s, то прибыль определяется по формуле (t·10⁹ - s). Компании необходимо разработать стратегию проведения экспериментов, позволяющую максимизировать прибыль, которую можно гарантированно получить.

В зависимости от результатов предыдущих экспериментов стратегия определяет, эксперимент какого типа следует провести, или решает прекратить дальнейшее выполнение экспериментов. Стратегия позволяет гарантированно получить прибыль x, если при любых результатах проведения экспериментов: во-первых, в контейнере реактора оказывается не более a граммов антивещества, во-вторых, прибыль составит не менее x.

Например, пусть возможен только один тип эксперимента, порождающий от 4 до 6 граммов антивещества, затраты на его проведение равны 10, а вместимость контейнера составляет 17 граммов. Тогда после двукратного проведения эксперимента в контейнере может оказаться от 8 до 12 граммов антивещества. Если получилось 12 граммов, то больше проводить эксперимент нельзя, так как в случае получения 6 граммов антивещества контейнер может переполниться. В остальных случаях можно провести эксперимент в третий раз и получить от 12 до 17 граммов антивещества. В худшем случае придётся провести эксперимент трижды, затратив в сумме 30, прибыль составит (12·10⁹ - 30) = 11 999 999 970.

Требуется написать программу, которая определяет максимальную прибыль x, которую гарантированно можно получить.

Юный Мирко решил купить куклу вуду. Учитывая что он крайне заинтересован в том, ктобы купить ее как можно дешевле, он начал отслеживать цены на кукол вуду каждый день. Его список состоит из цен на куклы в последние N дней, где a _i обозначает цену куклы i дней назад.

Мирко думает, что нашел связь между средней ценой кукол в течении нескольких последовательных дней и ценой куклы в следующий день. Он хочет проверить свою догадку и задался вопросом: "Для данного числа P , сколько существует наборов последовательных дней в течении последних N дней, для которых средняя цена куклы в эти дни составляет не менее P ".

Два набора последовательных дней считаются различными, если у них отличается первый или последний день.

Вам дан массив целых чисел длины N . Пусть s ₁ , s ₂ , ... , s _q - массив его непустых подпоследовательностей, отсортированный в лексикографическом порядке.

Подпоследовательностью массива называется массив, полученным путем вычеркивания нескольких (возможно, 0) элементов из изначального массива. Заметьте, что некоторые подпоследовательности могут быть одинаковыми, поэтому q = 2 ^N - 1 .

Массив A лексикографически меньше массива B , если A _i < B _i , где i - первая позиция, в которой массивы различаются, или если A - строгий префикс B .

Определим хеш массива s , состоящего из элементов v ₁ , v ₂ , ... , v _p , как: h ( s )  =  ( v ₁ · B ^{p - 1} + v ₂ · B ^{p - 2} + ... + v _{p - 1} · B + v _p ) mod M , где B и M - данные числа.

Посчитайте h ( s ₁ ) , h ( s ₂ ) , ... , h ( s _K ) для данного K .