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

В очередной раз Аня открыла приложение VK Музыка и увидела семь новых плейлистов. У каждого из них был указан процент совместимости с музыкальными вкусами Ани. Аня решила, что послушает только те плейлисты, которые подходят под её вкусы не менее, чем на 90 процентов.

Подскажите Ане, сколько плейлистов она послушает.

Вам дана строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв. Определите, можно ли, используя ее символы, составить ровно $$$m$$$ палиндромов так, чтобы каждый символ входил ровно в один палиндром?

Строка является палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки «abacaba», «cccc», «z» и «dxd» являются палиндромами, а строки «abab» и «aaabaa» — нет.

Например, пусть $$$s$$$ = «ababcab», $$$n = 7$$$, $$$m = 3$$$. Тогда из ее букв можно составить $$$3$$$ палиндрома:

• «aba»
• «bcb»
• «a»

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

Великий царь Гильгамеш преследует Эмию и уже добрался до его поместья. За один час Гильгамеш одновременно уничтожает все комнаты из которых выходит наибольшее количество коридоров. Вместе в комнатой уничтожаются все коридоры, которыми она была связана с какими-то другими комнатами.

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

Помогите Кирицугу определить, какое максимальное количество часов он сможет прятаться от Гильгамеша.

Женя решил подготовить на Новый Год украшения на ёлку. А самое лучшее украшение — это правильный шестиугольник! Поэтому Женя поручил своей младшей сестре Кате сделать несколько правильных шестиугольников.

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

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

1. $$$\frac{\mathrm{SideMax}}{\mathrm{SideMin}} \le \frac{111}{100}$$$, где $$$\mathrm{SideMax}$$$ и $$$\mathrm{SideMin}$$$ — максимальная и минимальная длина стороны многоугольника.
2. $$$\frac{\mathrm{DiagMax}}{\mathrm{DiagMin}} \le \frac{111}{100}$$$, где $$$\mathrm{DiagMax}$$$ и $$$\mathrm{DiagMin}$$$ — максимальная и минимальная длина диагонали, соединяющей противоположные вершины шестиугольника.
3. Внутри шестиугольника существует точка $$$O$$$ в узле сетки такая, что $$$\frac{\mathrm{DistMax}}{\mathrm{DistMin}} \le \frac{111}{100}$$$, где $$$\mathrm{DistMax}$$$ и $$$\mathrm{DistMin}$$$ — максимальная и минимальная длина отрезка соединяющего точку $$$O$$$ с вершиной шестиугольника.

Аналитик Жора работает в маленькой компании, где он должен выполнять определенные вычисления. Еще десять лет назад ему выдали массив чисел. После этого каждый день он должен был вычислять сумму чисел на отрезке, концы которого задавали ему утром.

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

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

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

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

Будем считать, что массив Жоры состоит из $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$. Запросы, которые необходимо выполнять, бывают трех типов:

• $$$1$$$ $$$k$$$ — запрос первого типа, в котором необходимо все элементы массива возвести в степень $$$k$$$. Если после выполнения этого запроса хотя бы одно число станет больше, чем $$$10^5$$$, то этот запрос нужно проигнорировать.
• $$$2$$$ $$$k$$$ — запрос второго типа, в котором необходимо из всех элементов массива извлечь корень степени $$$k$$$. Если после выполнения этого запроса хотя бы одно число перестанет быть целым, то этот запрос нужно проигнорировать.
• $$$3$$$ $$$l$$$ $$$r$$$ — запрос третьего типа, в котором необходимо вычислить сумму элементов с номерами от $$$l$$$ до $$$r$$$ включительно.

В Берляндии открылось метро. Жители рады новому виду транспорта, а особенно рад мэр города. Однако всегда есть что улучшить.

Метро представляет собой связный граф с $$$n$$$ вершинами и $$$n-1$$$ ребрами. Мэр хочет улучшить метро, делает он это с помощью приказов. Приказы бывают двух видов:

• $$$+$$$ $$$v$$$: Построить новую станцию и соединить ее со станцией $$$v$$$. Если номер последней построенной станции был $$$x$$$, то номер новой станции будет $$$x+1$$$
• $$$-$$$ $$$v$$$: Разрушить станцию $$$v$$$. Гарантируется, что после удаления этой станции, схема метро остается связной, то есть от любой станции можно добраться до любой другой.

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