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