Bəli, bu baş verdi! İlk konteak! Gəlmələr Yerdə \textbf{2010-}da olacaqlar! Və onlar mövcud yer texnologiyalarından istifadə etməklə yığılması mümkün olmayan müəmmalı qurğu gətirməyi söz vermişdilər. Yer kürəsinin əksər alimləri belə düşünürlər! Bütün qəzetlər artıq bunun haqqında məqalələr nəşr etmişlər. Qurğunun girişinə \{\textbf{a_i}\} ardıcıllığı verilir. Sonra onun üzərində növbəti iki əməliyyat aparılır: \begin{enumerate} \item \[\textbf{l}; \textbf{r}\] intervalını seçirik və elə bütün \textbf{i}-lər üçün \textbf{a_i} ← \textbf{a_i^2 mod 2010} əməliyyatını yerinə yetiririk ki, \textbf{l} ≤ \textbf{i} ≤ \textbf{r} olsun. \item \[\textbf{l}; \textbf{r}\] intervalını seçirik və elə bütün \textbf{a_i} cəmini tapırıq ki, \textbf{l} ≤ \textbf{i} ≤ \textbf{r} olsun. Qeyd edək ki, cəm \textbf{2010} moduluna görə hesablanmır. \end{enumerate} Qəribədir, qurğu \textbf{50000} ədəddən ibarət çoxluq üzərində \textbf{50000}-ə qədər göstərilmiş şəkildə əməliyyat apara bilər. İndiyə qədər heç kim bunu edə bilməmişdir! Lakin Roman gəlmələrə inanmır və hesab edir ki, bu kiminsə birjada milyon dollar qazanması üçün böyük aldatmasıdır. O bunu sübut etmək istəyir. O Sizi qurğunun işini modelləşdirmək üçün tutmuşdur. \textbf{a_i} verilənlər ardıcıllığına və əməliyyatlar dəstinə görə, gəlmələrin müəmmalı qurğusunun işini modelləşdirən proqram yazın. \InputFile İlk sətir ardıcıllığın \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50 000}) uzunluğunu ehtiva edir. İkinci sətir başlanğıc ardıcıllığı ifadə edən \textbf{n} sayda \textbf{a_i} (\textbf{0} ≤ \textbf{a_i} ≤ \textbf{2009}) ədədlərini ehtiva edir. Üçüncü sətir əməliyyatların \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{50 000}) sayını ehtiva edir. Hər \textbf{m} sətrin hər biri əməliyyatı əks etdirir. \textbf{j}-ci əməliyyat onun \textbf{k_j} ('\textbf{1}' -- kvadrata yüksəltmə, '\textbf{2}' -- cəmi hesablama) tipini əks etdirir və ardınca da iki \textbf{l_j} və \textbf{r_j} (\textbf{1} ≤ \textbf{l_j} ≤ \textbf{r_j} ≤ \textbf{n}) tam ədədləri verilir. \OutputFile Hər bir ikinci tip əməliyyat üçün ayrı sətirdə cavabı vermək tələb olunur.