Второй тур подходил к концу, и Сарай уже думает сразу после тура пойти позаниматься в качалочку. Одно из любимых упражнений Сарая — это поднятие штанги. Штанга представляет из себя гриф с дисками, которые расположены в определённом порядке. То есть штангу можно представить массив $$$a$$$ размером $$$n$$$, где $$$a_i$$$ — вес $$$i$$$-го диска. Гарантируется, что все диски имеют различный вес.

Но чтобы нормально позаниматься, надо, чтобы штанга была сбалансирована. Штанга $$$k$$$-сбалансирована, если выполняется условие: $$$a_n = k$$$, $$$a_{n-1} = k-1$$$, $$$...$$$, $$$a_{n-k+1} = 1$$$. Чтобы привести штангу к $$$k$$$-сбалансированному состоянию, Сарай может поменять местами два соседних диска, но поскольку они тяжелые, надо выполнить это за минимальное количество действий.

Поскольку Сарай хочет попробовать разные способы балансировки, чтобы найти для себя идеальный, вы должны найти минимальное количество действий для всех $$$q$$$ запросов $$$k$$$-балансировок, которые интересны ему.

Второй тур кончился, чему очень рад Егор, ведь он не ставил фьючерсы уже целых $$$5$$$ часов.

Монеты, на которые Егор может поставить фьюч, можно представить в виде множества $$$S$$$ всех целых чисел от $$$1$$$ до $$$m$$$, то есть $$$ \{\, x \in S \mid 1 \leq x \leq m \, \} $$$. Но поскольку не на все монеты выгодно ставить деньги, у него есть специальное подмножество самых прибыльных монет $$$P$$$ размером $$$n$$$.

Но зайдя в бинанс Егор ужаснулся — какой-то гад поставил фьючи на все монеты сразу. Ему надо срочно все исправить, то есть сделать из множества $$$S$$$ множество $$$P$$$. Сделать это он может с помощью двух операций:

• Удалить любой элемент из множества $$$S$$$. Из-за комиссии стоимость данной операции $$$1$$$ near.
• Удалить элемент из множества $$$S$$$ равный $$$MEX-i$$$, где $$$MEX$$$ — это минимальное натуральное число, которое не встречается в множестве $$$S$$$, $$$i$$$ — это номер текущий операции в единичной индексации. Стоимость данной операции $$$0$$$ near.

Помогите Егору получить множество $$$P$$$ из $$$S$$$ за минимальное количество near.

Определим $$$ A = S \setminus P $$$. То есть $$$ A $$$  — множество элементов, которые необходимо удалить.

После второго тура Дольчик решил отпраздновать окончание респы. Было решено организовать After party.

После $$$5$$$ выпитых бутылок липтона из окна полетели зарядки, пиццы и т.д. На звуки громкой музыки пришел Александр, которому стало интересно, что тут происходит. Зайдя в комнату, он увидел немного пьяного Дольчика. Хоть тот и всё отрицал, но Александр что-то заподозрил. Поэтому он решил устроить ему проверку трезвости.

Александр дал Дольчику массив строк $$$s$$$ размером $$$n$$$ и целое число $$$k$$$. Рассмотрим множество всех таких непустых строк, которые встречаются как подстроки во всех строках массива $$$s$$$ одновременно. И Александр просит Дольчика найти $$$k$$$-ую в лексикографическом порядке строку из этого множества.

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

Заходя в вагон поезда, Михаил заметил странную наполовину закрашенную надпись — " Made in Po... ". Не обратив сильно внимания, он сел на свое место, и поезд тронулся.

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

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

В этой игре в самом начале дается массив натуральных чисел $$$a$$$ размером $$$n$$$ и целое число $$$k$$$.

В свой ход игрок должен придумать массив $$$c$$$ $$$(0 \leq c_i \leq k,$$$ $$$ \sum c_i = k)$$$ размером $$$n$$$. После этого он находит число $$$S = \sum a_i \cdot c_i$$$. И если данное число $$$S$$$, получалось в предыдущих ходах у кого-то из игроков, данный игрок проигрывает.

Поскольку Миша умный спортпрогер, он сразу понял, что ответ зависит от четности количества различных $$$S$$$, которые могут получиться. Поэтому он просит вас помочь ему найти количество различных $$$S$$$.