Чебурашка та крокодил Гена

Коли Чебурашці та крокодилу Гені нічого робити, вони грають у різні цікаві ігри. Сьогодні Гена придумав нову гру, яка, на його думку, допоможе Чебурашці вивчити арифметику. Правила гри дуже прості: Гена візьме $n$ дощечок, пронумерує їх від $1$ до $n$ і напише на них якісь числа. Після чого він буде казати два числа $l$ та $r$, а Чебурашка повинен буде порахувати суму усіх чисел на дощечках з номерами від $l$ до $r$.

Також, щоб Чебурашка не вивчив усі можливі відповіді, Гена іноді змінює деякі числа на інші, а саме усі числа на проміжку $[l,r]$. Він не хоче сильно думати, тому просто пише на цих дощечках числа від $1$ до $r-l+1$ по порядку. Чебурашка поки що не дуже добре знає арифметику, тому просить Вас написати йому програму, яка допоможе йому у цьому.

Вхідні дані

У першому рядку знаходиться одне число $n(1\le n\le 10^6)$ — кількість дощечок. У наступному рядку знаходиться $n$ чисел — початкові значення, написані на дощечках (усі числа не перевищують $10^9$). Далі йде число $m(1\le m\le 10^5)$ — кількість запитів. Потім йде $m$ рядків, перше число у рядку — це вид запиту $t(1\le t\le 2)$.

• Якщо $t=1$, то далі йдуть два числа $l$ та $r$. Вам потрібно порахувати суму усіх чисел на дощечках з номерами від $l$ до $r$;

• Якщо $t=2$, то далі йдуть два числа $l$ та $r$. Це означає, что на дощечках з номерами від $l$ до $r$ будуть тепер числа від $1$ до $r-l+1$ відповідно.

Гарантується, що усі проміжки коректні. Нумерація дощечок починається з одиниці.

Вихідні дані

Для кожного запиту з номером $1$ виведіть суму чисел на проміжку $[l,r]$.

Приклади