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

Поднявшись на гору, он увидел 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 соответственно.