Да, это случилось! Первый контакт! Пришельцы прибудут на Землю в \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 Для каждой операции второго типа в отдельной строке следует вывести ответ.