Когда Чебурашке и крокодилу Гене нечего делать, они играют в разные интересные игры. Сегодня Гена придумал новую игру, которая, по его мнению, поможет Чебурашке выучить арифметику. Правила игры очень просты: Гена возьмет дощечек, пронумерует их от до и напишет на них какие-то числа. После чего он будет говорить два числа и , а Чебурашка будет должен посчитать сумму всех чисел на дощечках с номерами от до .
Также, чтобы Чебурашка не выучил все возможные ответы, Гена иногда меняет некоторые числа на другие, а именно все числа на промежутке . Он не хочет сильно думать, поэтому просто пишет на этих дощечках числа от до по порядку. Чебурашка пока не очень хорошо знает арифметику, поэтому просит Вас написать ему программу, которая поможет ему в этом.
В первой строке находится количество дощечек . В следующей строке находится чисел — начальные значения, написанные на дощечках (все числа не превышают ). Далее следует количество запросов . Затем идет строк, первое число в строке — это вид запроса .
Если , то далее следуют два числа и . Вам надо посчитать сумму всех чисел на дощечках с номерами от до ;
Если , то далее следуют два числа и . Это означает, что на дощечках с номерами от до будут теперь числа от до соответственно.
Гарантируется, что все промежутки корректны. Нумерация дощечек начинается с единицы.
Для каждого запроса с номером выведите сумму чисел на промежутке .