Великий бій#11030

Великий бій

4 секунди

128 мегабайтів

Складна

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

Піднявшись на гору, він побачив $n$ богів. Спостерігаючи за ними, Кратос оцінив силу кожного. Бог з номером $i$ має силу $s_{i}$ s_i.

Битися з богами непросто, тому після бою з $i$ -м богом сила Кратоса $t$ стає рівною $⌊ t / s_{i} ⌋$ \lfloor t / s_i \rfloor. Коли $t$ зменшується до нуля, Кратос гине.

З часом деякі поруч стоячі боги втомлюються, і їхня сила зменшується на одиницю. Іншими словами, Кратосу надходить запит $(l, r)$ (l, r), який означає, що для кожного бога $i$ , що стоїть на позиції з $l$ по $r$ , $s_{i} = max (s_{i} - 1, 1)$ s_i = \max(s_i - 1, 1).

Кратос придумує плани під час бою. План під номером $j$ полягає в тому, що Кратос буде битися по черзі з богами з номерами $l_{j}, l_{j} + 1, \dots, r_{j}$ l_j, l_j + 1, \ldots, r_j. При цьому початкова сила Кратоса буде рівна $x_{j}$ x_j. Для кожного плану він хоче дізнатися, чи зможе він вижити після його виконання. Якщо Кратос загине, то він хоче дізнатися, який бог завдасть йому останнього удару.

Допоможіть Кратосу і для кожного плану виведіть номер бога, який уб'є Кратоса. Якщо Кратос залишиться живим, то виведіть $- 1$ .

Вхідні дані

У першому рядку міститься два цілих числа $n$ і $q$ $(1 \leq n, q \leq 500000)$ (1 \le n, q \le 500000) - кількість богів і кількість запитів. У другому рядку міститься $n$ цілих чисел $s_{1}, s_{2}, \dots, s_{n}$ s_1, s_2, \ldots, s_n $(1 \leq s_{i} \leq 1 0^{9})$ (1 \le s_i \le 10^9) - сили богів. Кожен з наступних $q$ рядків містить запити у наступному форматі.

Спочатку йде тип запиту $t y p e$ . Якщо $t y p e = 1$ type = 1, то далі в рядку містяться два цілі числа $l$ і $r$ $(1 \leq l \leq r \leq n)$ (1 \le l \le r \le n), що означають, що сила богів з номерами від $l$ до $r$ зменшилася.

Якщо $t y p e = 2$ type = 2, то далі в рядку містяться три цілі числа $l$ , $r$ , $x$ $(1 \leq l \leq r \leq n, 1 \leq x \leq 1 0^{9})$ (1 \le l \le r \le n, 1 \le x \le 10^9) - номер першого бога, номер останнього бога і початкова сила Кратоса в черговому плані.

Вихідні дані

Після кожного запиту другого типу виведіть номер бога, який уб'є Кратоса. Якщо після виконання плану Кратос залишиться живим, то виведіть $- 1$ .

Приклади

Приклад 1

Приклад 2

Примітка

У першому запиті першого прикладу початкова сила Кратоса дорівнює $61$ . Після першого бою вона дорівнює $⌊ 61/1 ⌋ = 61$ \lfloor 61 / 1 \rfloor = 61. Потім вона дорівнює $30$ , $10$ , $5$ , $1$ , $1$ і $1$ відповідно.