28799번 - Великий бой 다국어

Оправившись после прошлого боя, Кратос снова отправляется в поход. Он решил подняться на Гору Олимп вместе с Титанами и устроить самое грандиозное сражение.

Поднявшись на гору, он увидел $n$ богов. Понаблюдав за ними, Кратос оценил силу каждого. Бог с номером $i$ обладает силой $s_i$.

Сражаться с богами непросто, поэтому после боя с $i$-м богом сила Кратоса $T$ становится равной $\lfloor \frac{T}{s_i} \rfloor$. Когда $T$ уменьшается до нуля, Кратос погибает.

Со временем некоторые рядом стоящие боги устают, и их сила уменьшается на единицу. Другими словами, Кратосу поступает запрос ($l$, $r$), который означает, что для каждого бога $i$, стоящего на позиции с $l$ по $r$, $s_i = \max(s_i - 1, 1)$.

Кратос придумывает планы по ходу боя. План под номером $j$ заключается в том, что Кратос будет сражаться по очереди с богами с номерами $l_j$, $l_j + 1$, $\dots$, $r_j$. При этом начальная сила Кратоса будет равна $x_j$. Для каждого плана он хочет узнать, сможет ли он выжить после его исполнения. Если Кратос погибнет, то он хочет узнать какой бог нанесет ему последний удар.

Помогите Кратосу и для каждого плана выведите номер бога, который убьет Кратоса. Если Кратос останется жив, то выведите <<-1>>.

В первой строке входных данных содержится два целых числа $n$ и $q$ --- количество богов и количество запросов ($1 \leq n, q, \leq 500\,000$). Во второй строке содержится $n$ целых чисел $s_1$, $s_2$, $\dots$, $s_n$ --- силы богов ($1 \leq s_i \leq 10^9$). Каждая из последующий $q$ строк содержит запросы в следующем формате.

Сначала следует тип запроса $type$. Если $type = 1$, то далее в строке содержатся два целых числа $l$ и $r$, означающих, что сила богов с номерами от $l$ до $r$ уменьшилась ($1 \leq l \leq r \leq n$).

Если $type = 2$, то далее в строке содержатся три целых числа $l$, $r$, $x$ --- номер первого бога, номер последнего бога и начальная сила Кратоса в очередном плане ($1 \leq l \leq r \leq n, 1 \leq x \leq 10^9$).

После каждого запроса второго типа выведите номер бога, который убьет Кратоса. Если после исполнения плана Кратос останется жив, то выведите <<-1>>.

В первом запросе первого примера начальная сила Кратоса равна 61. После первого сражения она равна $\lfloor \frac{61}{1} \rfloor = 61$. Затем она равна 30, 10, 5, 1, 1 и 1 соответственно.