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

Будем называть целое число $$$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$$$-степенным?

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

After a tough contest, it can be helpful to drink some coffee. Real programmers have many different types of coffee that are gradually added to one cup. We will consider coffee with a specific feature: different types of coffee are layered in the cup and do not mix.

A drink made from such types of coffee can be described as follows: there are a total of $$$n$$$ types of coffee in the cup, the $$$i$$$-th type is characterized by its strength level $$$p_i$$$ and the height of the layer it occupies in the cup, $$$h_i$$$. If $$$i \lt j$$$, then the layer of the $$$i$$$-th type of coffee is below the coffee of the $$$j$$$-th type. It is also known that the height of the cup is equal to $$$\sum\limits_{i=1}^n h_i$$$, meaning the top edge of the uppermost layer of coffee is exactly at the upper boundary of the cup.

Sometimes you want to create a drink with a specific total strength level. The total strength level is defined as the weighted average of the levels of the types of coffee poured into the cup, that is, $$$$$$P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}$$$$$$

To change $$$P$$$, one can:

1. choose a straw of arbitrary height $$$h$$$;
2. perform the following one or more times: put the straw into the drink to any depth from $$$0$$$ to $$$h$$$ inclusive relative to the top edge of the cup (not relative to the current liquid level) and sip an arbitrary (not necessarily whole) amount of coffee from the level where the bottom end of the straw reaches.

When sipping some amount of coffee from one layer, the height of that layer decreases by the corresponding amount, and all upper layers drop down by the same amount.

Your task is to answer queries of the form: can the current drink be turned into a drink with strength $$$t_i$$$, and if so, what is the minimum height of the straw required for this? Since it may be difficult to calculate the exact necessary height of the straw, it is sufficient to determine the minimum number of upper layers of coffee needed so that by sipping some amount of coffee from some of them, it is possible to achieve a total strength level of $$$t_i$$$.

На клетчатой доске размером $$$n \times m$$$, состоящей из $$$n$$$ строк и $$$m$$$ столбцов, в клетке $$$(r, c)$$$, то есть на пересечении $$$r$$$-й сверху строки и $$$c$$$-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

1. Компьютер называет целое число $$$k \gt 0$$$.
2. Вы ровно $$$k$$$ раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.
3. Компьютер называет координаты $$$(i, j)$$$ произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

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

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

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

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

То есть, если вы проигрываете игру на каком-либо тесте группы, вы получаете вердикт WA за соответствующий тест и $$$0$$$ баллов за всю группу. Иначе, если $$$R(\mathtt{group})$$$ — максимальное число баллов за группу, а $$$j(\mathtt{test})$$$ и $$$p(\mathtt{test})$$$ — ответы на тест программы жюри и вашей программы, соответственно, вы получаете за группу $$$$$$\left\lfloor R(\mathtt{group}) \cdot \min\limits_{\mathtt{test} \in \mathtt{group}} \frac{j(\mathtt{test})}{p(\mathtt{test})} \right\rfloor \text{ баллов.}$$$$$$

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

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

Изначально вам дан пустой стек и пустой массив. Кодом массива $$$a$$$ назовем последовательность действий вида

• $$$\mathtt{push}(x)$$$ — положить число $$$x$$$ на вершину стека;
• $$$\mathtt{pop}$$$ — снять число с вершины стека;
• $$$\mathtt{print}$$$ — выписать в конец массива все элементы стека по порядку от нижнего к верхнему,

Например, при выполнении последовательности действий $$$\mathtt{push}(1)$$$, $$$\mathtt{push}(2)$$$, $$$\mathtt{print}$$$, $$$\mathtt{print}$$$, $$$\mathtt{pop}$$$ и $$$\mathtt{print}$$$ в массив оказываются выписаны числа $$$[1, 2, 1, 2, 1]$$$, а на стеке остается лежать только число $$$1$$$. То есть такая последовательность является кодом массива $$$[1, 2, 1, 2, 1]$$$ длины $$$6$$$.

Вам дан массив $$$a$$$ и $$$q$$$ запросов: какой у отрезка массива $$$a$$$ с $$$l_i$$$-го по $$$r_i$$$-й элемент включительно минимальный по количеству действий со стеком код?

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач пройдены с положительным вердиктом. То есть, если вы получаете вердикт WA на каком-либо тесте в группе, вы получаете $$$0$$$ баллов за всю группу. Если все тесты группы пройдены с положительным вердиктом, вы получаете сумму баллов за все тесты в группе.

Для каждой подзадачи даны общие для тестов этой подзадачи ограничения и параметр $$$\gamma$$$, показывающий, насколько близкое к ответу жюри решение будет засчитываться на ненулевой балл.

Если ваше решение для $$$i$$$-го запроса в конкретном тесте строит код из $$$p_i$$$ действий, а решение жюри строит код из $$$j_i$$$ действий, то за этот тест ваше решение получает $$$$$$\max\left(0, \mathtt{score} - \max\left(0, \max\limits_{i=1}^q \left\lfloor\frac{p_i - j_i}{\gamma}\right\rfloor\right)\right) \text{ баллов,}$$$$$$ где $$$\mathtt{score}$$$ — максимальный балл за этот тест. Иными словами, за каждые $$$\gamma$$$ действий свыше решения жюри в каком-либо из запросов вы теряете один балл за тест.

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

Некоторые IT-компании проводят ежегодное глобальное мероприятие для сотрудников, на котором подводятся итоги года и обсуждаются ключевые точки в развитии всех проектов. В одной из компаний, на которой мы сфокусируемся, планируется обсуждение $$$k$$$ различных ее проектов.

Для того, чтобы мероприятие прошло интересно, необходимо выбрать хороших спикеров. Есть $$$n$$$ кандидатов, $$$i$$$-й из которых характеризуется своей осведомленностью о проектах — целым числом $$$a_i$$$ от $$$0$$$ до $$$2^k - 1$$$. При этом некоторые из кандидатов дружат между собой, а именно, есть $$$m$$$ пар друзей $$$(f_i, s_i)$$$.

Разумеется, всем хочется, чтобы мероприятие прошло гладко, а для этого необходимо, чтобы все спикеры попарно дружили между собой. При этом, чтобы рассказы спикеров не казались однообразными, важно, чтобы количество выбранных спикеров было как можно больше. Осведомленностью группы размера $$$s$$$, состоящей из кандидатов $$$i_1, i_2, \ldots, i_s$$$, называется $$$a_{i_1} \oplus a_{i_2} \oplus \ldots a_{i_s}$$$, где $$$\oplus$$$ — операция побитового исключающего «ИЛИ». Соответственно, помимо уже описанных критериев, среди всех подходящих групп кандидатов максимального размера необходимо выбрать группу спикеров с максимальной осведомленностью.

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

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

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

Все указанные ограничения распространяются на все наборы входных данных в каждом тесте соответствующей группы.

Последняя подзадача имеет потестовую оценку и содержит $$$7$$$ тестов, каждый из которых независимо оценивается в $$$4$$$ балла.