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