В далекой стране есть N городов. Был избран новый премьер-министр. В настоящее время в этой стране нет ни одной дороги, поэтому премьер-министр решил модернизировать страну, соединив некоторые города с двусторонними автострадами в транспортные сети. Два города будут расположены в одной и той же сети, если можно добраться до одного города от другого, используя недавно построенные дороги. Каждый город будет расположен в какой-то сети. Каждая сеть состоит из одного или нескольких городов.

Города представлены в виде точек в двумерной системе координат. Дорога между двумя городами представлена ​​в виде отрезка, соединяющего две точки, в которых расположены города. Длина дороги равна длине отрезка в километрах.

В настоящее время страна переживает экономический спад, поэтому премьер-министр решил, что из-за отсутствия бюджета они не будут строить дороги длиннее, чем D километров. Кроме того, премьер-министр радуется мелочам, поэтому он будет счастлив, если по крайней мере в одной сети будет существовать непустое подмножество городов (оно может включать все города в сети), где общая сумма жителей делится на К . Например, если K = 4 и есть сеть с городами, в которых есть 3 , 5 , 7 жителей соответственно, премьер-министр будет счастлив, потому что сумма жителей в первых двух городах равна 8 .

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

Марко обнаружил новую функцию на его телефоне - Т9. На его телефоне имеется стандартная клавиатура на 9 кнопок:

Для того чтобы вводить текст на этой клавиатуре необходимо несколько раз нажимать клавишу с соответствующей буквой. Точнее, если это первая буква на клавише, нужно нажать 1 раз, если вторая буква - 2 раза, и так далее. Например, если мы хотим ввести слово "giht", то необходимо нажать клавиши следующим образом: g-4 i-444 h-44 t-8. Новая возможность, которую открыл Марко, упрощает ввод текста, потому что больше не требуется нажимать по одной клавише несколько раз подряд - достаточно всего одного нажатия. Программа будет пытаться понять, какое слово из словаря вы пытаетесь ввести.

Марко довольно скептически относится к новым технологиями (как минимум к новым для него) и он боится, что ошибки будут довольно часто. Марко наизусть знает весь словарь мобильного телефона. Он состоит из N слов, состоящих из строчных латинских букв, длина каждого слова не превышает 1000000 символов. Марко даст массив нажатий на клавиши S длиной не более 1000, и хочет узнать как много слов из словаря он может получить при такой последовательности нажатий если используется функция Т9.

Банк страны Олимпия пригласил Петрика проверить новую систему безопасности. Его задача как можно скорее открыть сейф, разгадав такой шифр. Вокруг центрального круга сейфа записано p натуральных чисел. Для того, чтобы открыть сейф, необходимо заменить все числа на другие натуральные таким образом, что каждое число в сумме с q - 1 следующим числами давало бы первоначальное число. Например, если вокруг круга сейфа указано числа 11, 12, 11, 9, 9, 9, 9, и q = 5 , то нужно установить числа 1, 2, 3, 2, 3, 2, 1 и сейф будет открыт!

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

Петрик обожает конструкторы. В этот раз он захотел поиграть с набором прямоугольных брусков. Этот набор состоит из n брусков, причем содержит ровно по одному бруску каждого из размеров 1 * 1, 1 * 2, ..., 1 * n. Петрик хочет выбрать некоторые бруски из набора и построить из них пирамидку. Пирамидка состоит из одного или более уровней высотой в один кубик, в каждом уровне бруски расположены горизонтально вплотную друг к другу меньшей стороной, а самый левый брусок в уровне расположен вплотную к стене, и каждый следующий уровень не более длиной, чем предыдущий (считая снизу вверх). При этом Петрик считает, что пирамидка будет более устойчивой, если каждый брусок в каждом уровне, кроме низкого, будет лежать не менее чем на двух брусках с предыдущего уровня. Например, такая конструкция не является пирамидкой, потому что брусок 1 * 2 лежит только на одном бруске: Найдите пирамидку с наибольшим количеством уровней, которую можно построить из некоторых брусков из данного набора с n брусков. Если таких пирамидок несколько, то выведите любую.

В распоряжении агрономического комбината «Олег и ко» находится n полей, пронумерованных от 1 до n . Для каждого поля определена его урожайность a _i ≤ 10 ⁹ — сколько килограмм винограда можно собрать с этого поля за год.

В связи с трудной экономической ситуацией руководству фирмы приходится принимать решительные (хоть и не совсем честные) меры по повышению стоимости акций предприятия. Руководство знает, что стоимость акций равна среднему арифметическому урожайностей полей, принадлежащих комбинату. Но эта величина может быть очень маленькой, поэтому руководство приняло решение сообщать при регистрации не обо всех полях, а лишь о каком-то множестве полей с последовательными индексами. Кроме того, некоторые поля не отвечают высоким стандартам производства винограда, поэтому регистрировать их нельзя (иначе фирму могут закрыть). Однако все знают, что у комбината более одного поля, поэтому регистрация одного поля будет выглядеть подозрительно, и, поэтому, директор всегда будет регистрировать не менее двух полей.

Вам необходимо помочь руководству фирмы и ответить на q запросов. Запросы могут быть одного из двух видов:

1 l r x — урожайность полей с номерами от l до r увеличиласть на x ( 1 ≤ x ≤ 10 ⁹ ).

2 l r — предположим, разрешено регистрировать поля с номерами от l до r ( 1 ≤ l < r ≤ n ). Какой максимальной прибыли может добиться директор при правильном выборе полей, которые он будет регистрировать?