Böyük döyüş
Kratos, keçmiş döyüşdən sonra yeni bir səfərə çıxır. O, Titanlarla birlikdə Olimpiya Dağına qalxaraq ən böyük döyüşü təşkil etməyə qərar verir.
Dağa çatdıqdan sonra Kratos n tanrı ilə qarşılaşır. O, hər bir tanrının gücünü qiymətləndirir. i nömrəli tanrının gücü s[i]-dir.
Tanrılarla döyüşmək çətindir, buna görə də i-ci tanrı ilə döyüşdən sonra Kratosun gücü t ⌊t / s[i]⌋ olur. t sıfıra düşərsə, Kratos məğlub olur.
Zamanla bəzi yan-yana duran tanrılar yorulur və onların gücü bir vahid azalır. Başqa sözlə, Kratosa (l, r) sorğusu gəlir, bu da l-dən r-ə qədər olan mövqedə duran hər bir i tanrısı üçün s[i] = max(s[i] − 1, 1) deməkdir.
Kratos döyüş zamanı planlar qurur. j nömrəli plan ondan ibarətdir ki, Kratos ardıcıl olaraq l[j], l[j + 1], ..., r[j] nömrəli tanrılarla döyüşəcək. Bu zaman Kratosun başlanğıc gücü x[j] olacaq. Hər bir plan üçün o, planın icrasından sonra sağ qalıb-qalmayacağını bilmək istəyir. Əgər Kratos ölərsə, o, hansı tanrının ona son zərbəni vuracağını bilmək istəyir.
Kratos'a kömək edin və hər bir plan üçün Kratosu öldürəcək tanrının nömrəsini çıxarın. Əgər Kratos sağ qalarsa, -1 çıxarın.
Giriş Məlumatları
Birinci sətirdə iki tam ədəd n və q (1 ≤ n, q ≤ 500000) - tanrıların sayı və sorğuların sayı. İkinci sətirdə n tam ədəd s[1], s[2], ..., s[n] (1 ≤ s[i] ≤ 10^9) - tanrıların gücləri. Sonrakı q sətirdən hər biri aşağıdakı formatda sorğuları ehtiva edir.
Əvvəlcə sorğunun növü type gəlir. Əgər type = 1, onda sətirdə iki tam ədəd l və r (1 ≤ l ≤ r ≤ n) gəlir, bu da l-dən r-ə qədər olan nömrəli tanrıların gücünün azaldığını bildirir.
Əgər type = 2, onda sətirdə üç tam ədəd l, r, x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10^9) gəlir - birinci tanrının nömrəsi, sonuncu tanrının nömrəsi və Kratosun növbəti plandakı başlanğıc gücü.
Çıxış Məlumatları
İkinci tipli hər bir sorğudan sonra Kratosu öldürəcək tanrının nömrəsini çıxarın. Əgər planın icrasından sonra Kratos sağ qalarsa, -1 çıxarın.
İzah
Birinci misalın birinci sorğusunda Kratosun başlanğıc gücü 61-dir. İlk döyüşdən sonra o, ⌊61 / 1⌋ = 61 olur. Sonra o, müvafiq olaraq 30, 10, 5, 1, 1 və 1 olur.