Великий бой

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

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

Сражаться с богами непросто, поэтому после боя с i-м богом сила Кратоса t становится равной ⌊t / s[i]⌋. Когда t уменьшается до нуля, Кратос погибает.

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

Кратос придумывает планы по ходу боя. План под номером j заключается в том, что Кратос будет сражаться по очереди с богами с номерами l[j] , l[j + 1], ..., r[j]. При этом начальная сила Кратоса будет равна x[j]. Для каждого плана он хочет узнать, сможет ли он выжить после его исполнения. Если Кратос погибнет, то он хочет узнать какой бог нанесет ему последний удар.

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

Входные данные

В первой строке содержится два целых числа n и q (1 ≤ n, q ≤ 500000) - количество богов и количество запросов. Во второй строке содержится n целых чисел s[1], s[2], ..., s[n] (1 ≤ s[i] ≤ 10^9) - силы богов. Каждая из последующий q строк содержит запросы в следующем формате.

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

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

Выходные данные

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

Примеры

Примечание

В первом запросе первого примера начальная сила Кратоса равна 61. После первого сражения она равна ⌊61 / 1⌋ = 61. Затем она равна 30, 10, 5, 1, 1 и 1 соответственно.