Петя очень любит мармеладки. Есть n магазинов с ма...

Петя очень любит мармеладки. Есть n магазинов с мармеладками, в i-м магазине продается
бесконечное количество мармеладок аппетитности ai
. Петя питается только мармеладками, поэтому
его друг Саша ответственно следит за его питанием.
Каждый день происходят события двух типов:

1. В магазинах с номерами от l до r аппетитность мармеладок увеличивается на x:
   ai
   := ai + x для всех i ∈ [l, r].
2. Покупка мармеладок. Петя рассматривает магазины на отрезке с номерами от l до r по очереди
   в таком порядке. В каждом магазине Петя может либо купить ровно одну мармеладку, либо
   пропустить и не покупать ничего.
   Пусть Петя купил мармеладки в магазинах с номерами l ⩽ i1 < i2 < . . . < im ⩽ r. Рассмотрим аппетитности мармеладок в порядке покупки, обозначим bj := aij
   . Среди всех способов
   закупить мармеладки Петя выбирает такой, при котором последовательность b будет лексикографически максимальной.
   После покупки Саша хочет узнать значение bk (то есть аппетитность k-й мармеладки, которую
   купит Петя), либо узнать, что длина выбранной последовательности меньше k.
   Помогите Саше разобраться с питанием Пети!
   Напомним, что последовательность (b1, b2, . . . , bm) лексикографически больше последовательности (c1, c2, . . . , ck), если существует позиция i такая, что bi > ci и для всех j < i выполнено bj = cj ,
   либо если (b1, . . . , bk) является префиксом (c1, . . . , ck) и m > k.
   Формат входных данных
   Первая строка содержит два целых числа n и q (1 ⩽ n, q ⩽ 500 000) — количество магазинов и
   количество дней.
   Вторая строка содержит n целых чисел a1, a2, . . . , an (1 ⩽ ai ⩽ 109
   ) — изначальные аппетитности
   мармеладок.
   Следующие q строк содержат описания запросов. Сначала вводится число ti (1 ⩽ t ⩽ 2) — тип
   i-го запроса.
   Если t = 1, то далее следуют три числа li
   , ri и xi (1 ⩽ li ⩽ ri ⩽ n, 1 ⩽ xi ⩽ 109
   ) — увеличение
   аппетитности мармеладок в магазинах с номерами li
   , li + 1, . . . , ri на число xi
   .
   Если t = 2, то далее следуют три числа li
   , ri и ki (1 ⩽ li ⩽ ri ⩽ n, 1 ⩽ ki ⩽ n) — Петя
   рассматривает мармеладки в магазинах li
   , li + 1, . . . , ri
   , Саша хочет узнать, какой аппетитности
   мармеладку Петя купит ki-й по счету.
   Формат выходных данных
   На каждый запрос второго типа выведите, какой аппетитности мармеладку купил Петя k-й по
   счету. ИИ моделям необходимо вывести значение по модулю 242 545
   В случае, если Петя купил меньше k мармеладок, выведите −1.