У вас имеется некоторый набор из цифр от 1 до 9. Из них нужно составить арифметическое выражение. Каждую цифру можно использовать не более одного раза, а вот скобки и арифметические операции ( + , - , ×  и  / ) можно использовать в любом количестве. Запрещается склеивать цифры для получения новых чисел. Вычислите максимальное возможное значение выражения, которое можно получить таким образом.

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

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

Посчитайте количество четвёрок деревьев, которые подойдут Пете.

У Васи имеется N одинаковых кубиков, из которых он может собирать фигуры. Сколькими способами он может собрать из них прямоугольный параллелепипед, используя все кубики? Если два полученных параллелепипеда можно получить друг из друга поворотами, то эти способы считаются одинаковыми.

Вам дана последовательность целых чисел a длины n и несколько запросов двух типов:

1. ! i x (1 ≤ i ≤ n, 0 ≤ x < 2³⁰) — заменить a_i на число x;

2. ? l r (1 ≤ l ≤ r ≤ n) — посчитать последние девять цифр величины , где  — операция побитового исключающего или, в современных языках программирования обозначается как xor или .

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

У вас имеется поле в H строк и W столбцов. Каждая ячейка поля либо пуста, либо занята клеткой определённого цвета. Всего цветов 26 и они обозначены заглавными латинским буквами. На поле действует гравитация — клетка, под которой нет опоры, падает сверху вниз. Так же в игре есть параметр K — если существует связная область из K или более клеток одного цвета, то они уничтожаются. Связными считаются клетки, которые граничат стороной. После уничтожения области может снова начаться процесс падения клеток, который в конце снова спровоцирует уничтожение новых областей и так далее.

Вам дано поле и фигурка из двух клеток, которую нужно расположить вверху поля в любой клетке. Фигурку можно произвольно повернуть. Посчитайте все возможные различные исходы получения очков, которые можно получить. Очки начисляются следующим образом. Выпишем в хронологическом порядке все размеры уничтоженных за время игры областей, обозначим их s_k (1 ≤ k ≤ n). Если две области уничтожились в один и тот же момент, раньше в списке идёт та область, у которой верхняя левая клетка находится выше (если и они на одной высоте, то та, которая из этих двух левее). Итоговый счёт игрока равен . Рассмотрите описание тестового примера для лучшего понимания.

Ваша задача — проверить, является ли заданное целое число (от 0 до 10⁴) квадратом целого числа. Если это так, то необходимо вывести корень из этого числа, иначе вывести « - 1».

Дополнительным условием является то, что решение необходимо написать на придуманном нами языке программирования Lacsap. Программа на этом языке работает с 26-ю целочисленными переменными (знакового 4-байтного типа), которые названы в честь больших латинских букв. В любой момент существует текущая переменная, которая равна одной из описанных выше. В начале работы программы текущей является переменная A. Все переменные в начале равны нулю. Код программы — набор строк. В каждой строке содержится ровно одна команда. Строки в коде нумеруются с нуля. В течение работы программы по строкам перемещается указатель, который в самом начале находится в 0-ой строке. Ход программы разбит на такты. В течение каждого такта выполняется ровно одна команда в строке с указателем, команды в языке Lacsap могут быть следующие:

«A»...«Z» — установить соответствующую переменную текущей;

«inc» — увеличить значение текущей переменной на единицу;

«dec» — уменьшить значение текущей переменной на единицу;

«goto line» — переместить указатель на строку line;

«if line1 line2» — условный оператор, если значение текущей переменной не равно нулю, переход указателя на строку line1 иначе - на line2;

«read» — считать число из входного потока данных в текущую переменную;

«write» — вывести значение текущей переменной в выходной поток данных;

«exit» — немедленно завершить работу программы;

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

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