Юный Мирко решил купить куклу вуду. Учитывая что он крайне заинтересован в том, ктобы купить ее как можно дешевле, он начал отслеживать цены на кукол вуду каждый день. Его список состоит из цен на куклы в последние N дней, где a _i обозначает цену куклы i дней назад.

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

Два набора последовательных дней считаются различными, если у них отличается первый или последний день.

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

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

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

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

В распоряжении агрономического комбината «Олег и ко» находится 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 ). Какой максимальной прибыли может добиться директор при правильном выборе полей, которые он будет регистрировать?

Одна очень известная корпорация проводит испытания новой модели собакоподобных роботов. Для этого главный инженер этой компании приобрёл бесконечную прямую в магазине «Всё для новорожденных» и положил по палке в каждой целочисленной точке этой прямой. Кроме того на прямой находится n роботов ( 1 ≤ n ≤ 2·10 ⁵ ). Так как у инженера плохое зрение, он не поставит робота на позицию, больше чем m ( 1 ≤ m ≤ 2·10 ⁵ ). Для каждого робота известна его позиция на прямой x _i — (целое число, 1 ≤ x _i ≤ m ).

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

Роботы-собаки очень нежные и ленивые существа, поэтому готовы приносить палки только в определённое время суток. Условно разобьём сутки на k моментов ( 1 ≤ k ≤ 2·10 ⁵ ), тогда робот с номером i выполнит команду, только если она поступила в момент времени не раньше l _i и не позже r _i ( 1 ≤ l _i ≤ r _i ≤ k ). В другие моменты времени собака просто останется на месте и не возьмёт палку даже если она находится прямо перед ней.

Главный инженер компании ещё не выбрал время проведения эксперимента. Для каждого момента времени от 1 до k сообщите какое минимальное суммарное расстояние преодолеют роботы, готовые работать в это время, если инженер выберет порядок отдачи команд оптимально.