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

Обозначим среднюю цену картошки в магазинах за P ₁ и P ₂ . Средняя цена равняется отношению суммарной стоимости к количеству картошки в данном магазине. Мистер Картошечка хочет, чтобы значение P ₁ · P ₂ было минимальным.

Кроме того, хотя бы в одном магазине дожно быть ровно L мешков картошки.

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

Оказывается, доска соответствует вполне понятным рекурсивным правилам. Первая клетка каждой строки содержит номер этой строки (начиная с 1). Значение же в каждой последующей клетке равно сумме значения в предыдущей клетке и перевернутого значения в предыдущей клетке. Перевернутое число можно получить, если записать в обратном порядке цифры десятичного представления числа.

Формально, если A ( i , j ) - значение в i -й строке и j -м столбце доски, то:

1. A ( i , 1) = i

2. A ( i , j ) = A ( i , j - 1) + rev ( A ( i , j - 1)) , если j > 1 .

rev ( x ) - операция разворота числа в его десятичном представлении. Например, rev (345) = 543 , а rev (1040) = 0401 = 401 .

Затем во сне Аника увидела дружелюбного призрака Бозо, появившегося из-за угла. Он сказал ей: "Аника! Если ты правильно ответишь на мои вопросы, я подарю тебе коробку вкусного печенья. А вопросы мои будут такие: я буду давать тебе по два числа A и B , а ты должна будешь сказать, сколько на доске чисел, лежащих в диапазоне [ A : B ] ".

Аника, хоть она и во сне, очень хочет поесть печенья, поэтому просит вас помочь ответить на вопросы Бозо.

Дан ориентированный граф. Подсчитайте, сколько пар вершин ( i , j ) имеют общего предка. Общим предком вершин i и j называется такая вершину k , что и i , и j достижимы из k .

Палиндром - это слово, которое читается справа налево также, как слева направо. Например, "a", "abba", "anavolimilovana" - палиндромы.

Весом строки, состоящей из строчных латинских символов будем называть количество ее подстрок (слов), являющихся палиндромами (при этом каждое вхождение подстроки считается отдельно). Формально, пусть W - строка длины N . Слово w _{a , b} - подстрока W , состоящая из символов на позициях с индексами с a по b включительно. Вес строки W - это количество пар целых чисел a , b ( 1 ≤ a , b ≤ N ) таких, что w _{a , b} является палиндромом.

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

Пусть дан строчный латинский символ c . Тогда операция shift ( c ) превращает c в следующий по порядку символ в алфавите. Например, shift (a) = b, shift (e) = f, shift (z) = a.

Дана строка S , состоящая из N строчных латинских символов (индексация с 0). Необходимо обработать Q запросов 2 типов:

"1 i j t": ко всем элементам строки с индексами в отрезке [i:j] применить t раз операцию shift .

"2 i j": найдите количество непустых подмножеств символов строки { c ₁ , c ₂ , ... , c _k }, где i ≤ index _{c 1} < index _{c 2} < ... < index _{c k} ≤ j , таких что символы подмножества, переставленные в некотором порядке, образуют палиндромом. Так как число может быть очень большим, выведите его по модулю 10 ⁹ + 7 .

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

Строка называется палиндромом, если читается слева направо также, как справа налево.