Загадочное устройство
Да, это случилось! Первый контакт! Пришельцы прибудут на Землю в 2010! И они пообещали привезти с собой загадочное устройство, которое невозможно собрать используя существующие земные технологии. Большая часть ученых мира думает именно так! Все газеты уже опубликовали передовые статьи об этом.
На вход устройства подается последовательность {a_i}. Затем над ней выполняются следующие две операции:
Выберем интервал [l; r] и выполним a_i ← a_i^2 mod 2010 для всех таких i, что l ≤ i ≤ r.
Выберем интервал [l; r] и выведем сумму всех a_i таких что l ≤ i ≤ r. Отметим, что сумма не вычисляется по модулю 2010.
Удивительно, что устройство способно выполнить до 50 000 операций указанного вида над последовательностью из 50 000 чисел за 3 секунды. Никто до этого не мог такого сделать!
Однако Роман не верит пришельцам и считает что это всего лишь чей-то большой обман с целью выиграть миллион долларов на бирже. Он хочет доказать это. Он нанял Вас промоделировать работу устройства.
По заданной последовательности a_i и набору операций напишите программу, которая промоделирует работу загадочного устройства пришельцев.
Входные данные
Первая строка содержит длину последовательности n (1 ≤ n ≤ 50 000). Вторая строка содержит n чисел a_i (0 ≤ a_i ≤ 2009), задающих начальную последовательность. Третья строка содержит количество операций m (1 ≤ m ≤ 50 000). Каждая из следующих m строк описывает операцию. j-ая операция описывается ее типом k_j ('1' - возведение в квадрат, '2' - вычисление суммы), за которой следуют два целых числа l_j и r_j (1 ≤ l_j ≤ r_j ≤ n).
Выходные данные
Для каждой операции второго типа в отдельной строке следует вывести ответ.