Bank
Olimbank gələcəkdə saatlıq mənfəətini proqnozlaşdırır və zaman-zaman bu məlumatları yeniləyir. Bankın analitikləri, proqnozun mövcud olduğu müxtəlif zaman aralıqlarını araşdırırlar. Hər bir belə zaman aralığı üçün analitiklər maraqlanır ki, bu aralıqda ən böyük orta saatlıq mənfəət dəyəri nədir. Yəni, verilmiş aralıq daxilində tamamilə yerləşən iki və ya daha çox saatlıq zaman kəsiyi tapmaq lazımdır ki, həmin kəsikdə mənfəət dəyərlərinin arifmetik ortası mümkün qədər böyük olsun. Bundan əlavə, müxtəlif analitiklər müxtəlif zaman aralıqları ilə maraqlanırlar.
Tapşırıq
Olimbankın mənfəətləri haqqında saatlıq proqnoz və bu proqnoza dəqiqləşdirmələr əsasında bankın analitiklərinin verilmiş zaman aralıqlarında maksimal orta saatlıq mənfəət haqqında sorğularına cavab verən proqram yazın.
Giriş məlumatları
Girişin birinci sətirində iki tam ədəd N və M verilir — proqnozun mövcud olduğu saatların sayı və iki növ əməliyyatın ümumi sayı: analitiklərin sorğuları və proqnozun dəqiqləşdirilməsi.İkinci sətirdə N tam ədəd var: i-ci ədəd A[i] (–10^8 ≤ A[i] ≤ 10^8) i-ci saat üçün ilkin proqnozu təyin edir (müsbət dəyərlər mənfəəti, mənfi dəyərlər xərcləri göstərir).Növbəti M sətir əməliyyatları təsvir edir. Hər sətirdə ilk ədəd əməliyyatın növünü göstərir: 1, əgər bu proqnozun dəqiqləşdirilməsidirsə, və ya 2, əgər bu analitikin sorğusudursa.
• Proqnozun dəqiqləşdirilməsi əməliyyatı halında, sətirdə daha üç tam ədəd L, R, X (1 ≤ L ≤ R ≤ N, –10^3 ≤ X ≤ 10^3, X ≠ 0) — proqnozun dəyişdirilməli olduğu aralığın sərhədləri (həmçinin sonlar daxil olmaqla) və bütün proqnoz dəyərlərinin X qədər dəyişdirilməsi lazımdır.
• Analitikin sorğusu halında, sətirdə daha iki tam ədəd L, R (1 ≤ L < R ≤ N) — sorğu aralığının sərhədləri (həmçinin sonlar daxil olmaqla).
Giriş məlumatlarında ən azı bir analitikin sorğusunun olması təmin edilir.
Çıxış məlumatları
Hər bir analitikin sorğusu üçün ayrı sətirdə iki tam ədəd L[M] və R[M] — maksimal orta mənfəət dəyərinin əldə edildiyi aralığın sonları (həmçinin daxil olmaqla) verin (burada L ≤ L[M] < R[M] ≤ R, L, R — müvafiq sorğunun sərhədləridir). Əgər belə aralıqlar bir neçə varsa, onlardan hər hansı birini verin.
Nümunələr
Qiymətləndirmə
Aşağıdakı əlavə şərtlər yerinə yetirilir:
2 ≤ N, M ≤ 100 — 15% testlər;
2 ≤ N, M ≤ 1000 — 35% testlər;
2 ≤ N, M ≤ 60000 — 50% testlər.