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

Задан набор букв $$$A$$$, состоящий из маленьких букв английского алфавита. Найдите два слова, $$$B$$$ и $$$C$$$, использующие все эти буквы (то есть, являющиеся анаграммами $$$A$$$), что $$$B$$$ и $$$C$$$ содержат разные буквы в каждой позиции. Составленные слова не обязаны быть реальными словами какого-либо языка.

Популярная компания Matryoshka Inc, производящая игрушки, планирует запустить акцию, в ходе которой всем желающим будет предложено решить следующую задачу: в ряд расставлены $$$n$$$ матрешек, пронумерованные от $$$1$$$ до $$$n$$$; $$$i$$$-я из них имеет размер $$$s_i$$$, причем $$$s_i$$$ может иметь лидирующие нули. Участникам предлагается собрать цепочку из как можно большего числа вложенных матрешек. Однако, есть ограничение, что собирать матрешки можно только в порядке слева направо, от меньшей к большей (матрешки можно пропускать, не обязательно использовать все подряд).

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

Директора компании заинтересовало, какой максимальный выигрыш сможет получить участник. Чтобы это выяснить, он отправил вам числа $$$s_1, \ldots, s_n$$$ по специальному секретному каналу связи компании Matryoshka Inc. Однако в ходе передачи сообщения произошел сбой, и цифры в числах $$$s_1, \ldots, s_n$$$ перемешались. В итоге вы получили набор чисел $$$a_1, \ldots, a_n$$$, где $$$a_i$$$ — число, полученное из $$$s_i$$$ некоторой перестановкой цифр.

Поскольку до запуска акции осталось всего ничего, времени на повторную отправку нет. Поэтому директор попросил вас найти максимальный возможный выигрыш участника по известным значениям $$$a_1, \ldots, a_n$$$. Учитывайте, что в теории настоящий размер $$$i$$$-й матрешки может быть равен любой перестановке цифр $$$a_i$$$, в том числе содержащей ведущие нули.

Обозначим за $$$L$$$ максимальную длину входного числа $$$a_i$$$.

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

Замок состоит из последовательности ячеек, на каждой из которых написано целое число. Ячейки можно менять местами, при правильной перестановке замок открывается. Замок откроется при следующем условии: для любой пары соседних ячеек сумма чисел на них не делится на $$$k$$$.

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

Рассмотрим бесконечную последовательность чисел $$$a_1, a_2, a_3, \ldots$$$. Последовательность называется само-описывающей, если $$$a_i$$$ равно количеству вхождений числа $$$i$$$ в эту последовательность.

Если наложить на последовательность условия $$$a_1 = 1$$$, а также то, что элементы не убывают, (то есть, $$$a_i \le a_{i+1}$$$ для всех $$$i$$$), то само-описывающая последовательность определяется уникально. Первые тридцать элементов последовательности выглядят так:

$$$$$$ 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, \ldots $$$$$$

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

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

В данной задаче эволюционную историю $$$n$$$ современных видов мы будем представлять в виде двоичного дерева с $$$n$$$ листьями, соответствующими этим $$$n$$$ видам. Каждая внутренняя вершина соответствует устаревшему виду, от которого в некоторый момент произошло, для простоты, два других. Корень дерева — условный «начальный» вид, от которого в итоге происходят все остальные. Листья в дереве имеют номера от $$$1$$$ до $$$n$$$, внутренние вершины имеют номера от $$$n + 1$$$ до $$$2n - 1$$$. Корень имеет номер $$$2n - 1$$$.

Чтобы сравнить две эволюционные теории, используют разные метрики; одна из них — расстояние по тройкам. Рассмотрим произвольные три различных вида (листа в дереве). Пойдем от этих видов вверх и найдем те два вида, в которых произошло разбиение, приведшее к тому, что существуют три современных вида. Для трех видов $$$A$$$, $$$B$$$ и $$$C$$$ есть, по сути, три способа развития (изображены на картинке): от общего предка в некоторый момент отделился вид, из которого в итоге произошли $$$A$$$ и $$$B$$$, а также еще один вид, из которого позже произошел $$$C$$$. Аналогично, есть два других варианта с другими разбиениями. Будем говорить, что история эволюции тройки $$$(A, B, C)$$$ отличается в двух эволюционных деревьях, если структура того, как они произошли, отличается в первой и второй теории. Ниже изображены три способа, как могут выглядеть истории эволюции трех видов, каждое ребро на картинке также может состоять из цепочки промежуточных видов.

Найдите число троек современных видов, структура развития которых различается в двух заданных теориях.