Великий бой
Великий бой
Оправившись после прошлого боя, Кратос снова отправляется в поход. Он решил подняться на Гору Олимп вместе с Титанами и устроить самое грандиозное сражение.
Поднявшись на гору, он увидел n богов. Понаблюдав за ними, Кратос оценил силу каждого. Бог с номером i обладает силой si
.
Сражаться с богами непросто, поэтому после боя с i-м богом сила Кратоса t становится равной ⌊t / si
⌋. Когда t уменьшается до нуля, Кратос погибает.
Со временем некоторые рядом стоящие боги устают, и их сила уменьшается на единицу. Другими словами, Кратосу поступает запрос (l, r), который означает, что для каждого бога i, стоящего на позиции с l по r, si
= max(si
− 1, 1).
Кратос придумывает планы по ходу боя. План под номером j заключается в том, что Кратос будет сражаться по очереди с богами с номерами lj
, lj+1
, ..., rj
. При этом начальная сила Кратоса будет равна xj
. Для каждого плана он хочет узнать, сможет ли он выжить после его исполнения. Если Кратос погибнет, то он хочет узнать какой бог нанесет ему последний удар.
Помогите Кратосу и для каждого плана выведите номер бога, который убьет Кратоса. Если Кратос останется жив, то выведите -1.
Входные данные
В первой строке содержится два целых числа n и q (1 ≤ n, q ≤ 500000) - количество богов и количество запросов. Во второй строке содержится n целых чисел s1
, s2
, ..., sn
(1 ≤ si
≤ 109
) - силы богов. Каждая из последующий q строк содержит запросы в следующем формате.
Сначала следует тип запроса type. Если type = 1, то далее в строке содержатся два целых числа l и r (1 ≤ l ≤ r ≤ n), означающих, что сила богов с номерами от l до r уменьшилась.
Если type = 2, то далее в строке содержатся три целых числа l, r, x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109
) - номер первого бога, номер последнего бога и начальная сила Кратоса в очередном плане.
Выходные данные
После каждого запроса второго типа выведите номер бога, который убьет Кратоса. Если после исполнения плана Кратос останется жив, то выведите -1.
Пояснение
В первом запросе первого примера начальная сила Кратоса равна 61. После первого сражения она равна ⌊61 / 1⌋ = 61. Затем она равна 30, 10, 5, 1, 1 и 1 соответственно.
6 4 1 2 3 2 3 1 2 1 6 61 2 1 3 2 1 1 3 2 1 3 2
-1 3 -1
3 3 100 200 300 2 2 3 500 1 1 3 2 1 3 5890598
3 3