Великий бій

Оправившись після минулого бою, Кратос знову вирушає в похід. Він вирішив піднятися на Гору Олімп разом з Титанами і влаштувати найграндіознішу битву.

Піднявшись на гору, він побачив 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 відповідно.