Великий бой
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оправившись после прошлого боя, Кратос снова отправляется в поход. Он решил подняться на Гору Олимп вместе с Титанами и устроить самое грандиозное сражение. Поднявшись на гору, он увидел $$$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».

Примеры

Входные данные
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

Примечание

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