Коли Чебурашці та крокодилу Гені нічого робити, вони грають у різні цікаві ігри. Сьогодні Гена придумав нову гру, яка, на його думку, допоможе Чебурашці вивчити арифметику. Правила гри дуже прості: Гена візьме n дощечок, пронумерує їх від 1 до n і напише на них якісь числа. Після чого він буде казати два числа l та r, а Чебурашка повинен буде порахувати суму усіх чисел на дощечках з номерами від l до r.
Також, щоб Чебурашка не вивчив усі можливі відповіді, Гена іноді змінює деякі числа на інші, а саме усі числа на проміжку [l,r]. Він не хоче сильно думати, тому просто пише на цих дощечках числа від 1 до r−l+1 по порядку. Чебурашка поки що не дуже добре знає арифметику, тому просить Вас написати йому програму, яка допоможе йому у цьому.
У першому рядку знаходиться одне число n (1≤n≤106) — кількість дощечок. У наступному рядку знаходиться n чисел — початкові значення, написані на дощечках (усі числа не перевищують 109). Далі йде число m (1≤m≤105) — кількість запитів. Потім йде m рядків, перше число у рядку — це вид запиту t (1≤t≤2).
Якщо t=1, то далі йдуть два числа l та r. Вам потрібно порахувати суму усіх чисел на дощечках з номерами від l до r;
Якщо t=2, то далі йдуть два числа l та r. Це означає, что на дощечках з номерами від l до r будуть тепер числа від 1 до r−l+1 відповідно.
Гарантується, що усі проміжки коректні. Нумерація дощечок починається з одиниці.
Для кожного запиту з номером 1 виведіть суму чисел на проміжку [l,r].