a1, a2, ..., an (0 ≤ ai ≤ 108, 2 ≤ n ≤ 105) ardıcıllığı verilir. İki tip əməliyyat vardır və onlar növbəti şəkildə təyin olunur:

Yeniləmə:

Bu girişdə 'U' kimi verilə bilər və boşluqdan sonra iki i və x tam ədədləri verilir.

U i x, 1 ≤ i ≤ n и 0 ≤ x ≤ 108

Bu əməliyyat x üçün ai qiymətlərini qurur.

Sorğu:

Bu girişdə 'Q' kimi verilə bilər və boşluqdan sonra iki i və j tam ədədləri verilir.

Q x y, 1 ≤ x < y ≤ n

Siz elə i və j tapmalısınız ki, x ≤ i, j ≤ y və i ≠ j, ai + aj cəmi ən böyük olsun. ai + aj cəmini verin.

Giriş verilənləri

İlk sətir ardıcıllığın uzunluğunu ifadə edən n tam ədədini ehtiva edir. Növbəti sətir boşluqla ayrılmış n sayda ai tam ədədlərini ehtiva edir. Növbəti sətir əməliyyatların sayını ifadə edən q (q ≤ 105) tam ədədini ehtiva edir. Növbəti q sayda sətirlər əməliyyatları ehtiva edir.

Çıxış verilənləri

Ayrı-ayrı sətirdə hər bir sorğu üçün maksimum cəmi verməli.