Обычно на вкладке «Положение участников» расположена таблица, в которой для каждого из участников напротив его позиции в рейтинге отображаются решённые им задачи.

Однако на сайте произошёл сбой, и теперь положение отобразилось как $$$n$$$ строк, каждая из которых состоит из не более чем $$$6$$$ неповторяющихся заглавных английских букв от A до F. Строки отобразились в соответствии с рейтингом участников, то есть количество решённых задач в каждой отобразившейся последующей строке не больше, чем в предыдущей.

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

Например, пусть в олимпиаде было $$$3$$$ участника и они решили следующие задачи:

1. A, B, E, F
2. A, B, C
3. B, C

Тогда всего было решено $$$5$$$ различных задач — A, B, C, E и F.

В Сбере решили создать новую команду, которая будет заниматься передовыми разработками искусственного интеллекта. Чтобы не допустить утечек технологий, было решено набрать команду только из текущих программистов Сбера. Для этого технический директор созвал $$$n$$$ человек для отбора. Все сотрудники расставлены в порядке начала работы в компании, а у каждого из них есть уровень навыка $$$a_i$$$. То есть 1-й сотрудник c навыком $$$a_1$$$ пришёл в компанию раньше 2-го сотрудника с навыком $$$a_2$$$, 2-й сотрудник с навыком $$$a_2$$$ пришёл раньше 3-го сотрудника с навыком $$$a_3$$$ и т.д.

Чтобы команда могла эффективно работать, важно, чтобы каждый сотрудник в ней чувствовал уверенность в поддержке коллег. Для этого было решено, что в любой группе сотрудников, выбранной для команды, у каждого участника должен быть человек, обладающий навыком не меньше, чем у него самого, и присутствующий среди тех, кто пришёл в компанию раньше него. Навык разработчика, пришедшего раньше всех из команды, может быть любым. Иными словами, среди сотрудников нужно найти подпоследовательность, в которой навык первого кандидата произвольный, а для других существует сотрудник со значением не меньше, чем у него среди предыдущих. Например, среди сотрудников с навыками $$$1, 3, 2$$$ можно выбрать в команду второго и третьего ($$$3 \ge 2$$$), но нельзя выбрать первого и третьего ($$$1 \lt 2$$$).

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

Артур Морган и Датч ван дер Линде решили отдохнуть после удачного ограбления, поэтому направились в салун в Валентайне. В салуне они нашли строку $$$s$$$, состоящую из маленьких букв латинского алфавита. В строке $$$s$$$ используются только восемь первых букв латинского алфавита («a», «b», «c», «d», «e», «f», «g», «h»). Длину строки $$$s$$$ обозначим как $$$|s|$$$.

Артур и Датч решили поиграть со строкой $$$s$$$ и поместили указатель $$$i$$$ на её первый символ (индексация с единицы). Игроки будут ходить по очереди, первым ходит Артур. В свой ход игрок забирает букву $$$s_i$$$ себе в пул, после чего сдвигает указатель $$$i$$$. Можно сдвинуть указатель $$$i$$$ на один вправо, при этом, если указатель стал больше $$$|s|$$$, игра немедленно заканчивается. Вместо этого, если $$$2 \cdot i \le |s|$$$, можно переместить указатель на позицию $$$2 \cdot i$$$ (если $$$2 \cdot i \gt |s|$$$, такой ход делать нельзя). Можно показать, что при таких условиях игра всегда закончится.

В конце игры Артур и Датч считают Побитовое исключающее ИЛИ букв в своих пулах. Букве «a» соответствует число $$$0$$$, букве «b» — число $$$1$$$, и т.д., букве «h» — число $$$7$$$. Например, Побитовое исключающее ИЛИ букв «a», «c», «h» равно $$$0 \oplus 2 \oplus 7 = 5$$$. Игрок, у которого значение Побитового исключающего ИЛИ больше, побеждает, при равенстве объявляется ничья.

Кто победит в игре, если Артур и Датч играют оптимально?

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

Эмия Кирицугу должен нарисовать неориентированный граф на $$$n$$$ вершинах. Рёбер можно проводить сколько угодно, но между каждой парой вершин должно быть не более одного ребра, кроме того нельзя проводить ребро из вершины в себя же. Получившийся граф не обязан быть связным.

Назовём граф легендарным, если в нём окажется ровно $$$k$$$ хороших пар вершин $$$\langle v, u \rangle$$$ ($$$1 \le v \lt u \le n$$$). Пара вершин называется хорошей, если между вершинами существуют ровно два простых пути, при этом они не пересекаются по рёбрам. Путь называется простым, если каждая вершина встречается в нём не более одного раза.

Вам нужно ответить на $$$q$$$ запросов. Каждый запрос задаёт числа $$$n$$$, $$$k$$$. Определите для каждого, получится ли у Эмии нарисовать легендарный граф.

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

Недавно она нашла на даче у своей бабушки растущее взвешенное дерево из $$$n$$$ вершин, у которого каждая вершина $$$i$$$ ($$$1 \le i \le n$$$) имеет вес $$$c_i$$$. Рядом с деревом лежала книга, где написано: «Напомним, что деревом называется граф без циклов, где между любыми двумя вершинами существует путь».

Мадока решила снять веселую нарезку взвешенного дерева и выложить её на набирающей популярность площадке «ТеремокТВ», где любое видео может легко набрать несколько десятков просмотров. Она хочет разбить бабушкино дерево на некоторое количество непересекающихся путей. Другими словами, каждая вершина должна принадлежать ровно одному простому пути.

Красотой простого пути $$$v_1, v_2, \ldots, v_k$$$ она считает значение $$$(c_{v_1} | c_{v_2} | \ldots | c_{v_k})^2$$$ (квадрат побитового ИЛИ весов вершин). Красотой разбиения будем считать сумму красот путей, на которые дерево распалось.

Помогите Мадоке стать популярной и набрать сотню просмотров. Найдите минимальную (у Мадоки очень странное понимание красоты) красоту дерева по всем его веселым нарезкам.

Ксюша поступила в престижный университет на Кипре. Программа первого семестра по алгебре содержала только лишь темы «Умножение целых чисел» и «Деление целых чисел». Ксюша училась в лучшей школе страны и уже проходила эти темы, поэтому она решила прогуливать лекции и семинары по алгебре.

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

Дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Необходимо ответить на $$$m$$$ запросов. Запросы бывают трёх типов:

1. посчитать $$$a_l \cdot a_{l+1} \cdot \ldots \cdot a_r$$$ по модулю $$$10^9 + 7$$$;
2. поделить каждое из чисел $$$a_l, a_{l+1}, \ldots, a_r$$$ на его минимальный нечётный делитель, больший $$$1$$$; если такого нет, число не меняется;
3. присвоить $$$a_i = x$$$.

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