eolymp
bolt
Try our new interface for solving problems
Problems

Enigmatic Device

Enigmatic Device

Yes, it happened! The first contact! Aliens will visit the Earth in \textbf{2010}! And they promised to bring an enigmatic device which cannot be constructed using existing Earth technologies. Most of the scientists of the world think so! All newspapers already published their leading articles about it. This device will accept an integer sequence \{\textbf{a_i}\} as its initial input. After that, it can perform the following two operations: \begin{enumerate} \item Take an interval \[\textbf{l}; \textbf{r}\] and perform \textbf{a_i} ← \textbf{a_i^2 mod 2010} for all ai such that \textbf{l} ≤ \textbf{i} ≤ \textbf{r}. \item Take an interval \[\textbf{l}; \textbf{r}\] and output the sum of all \textbf{a_i} such that \textbf{l} ≤ \textbf{i} ≤ \textbf{r}. Note that the sum is not taken modulo \textbf{2010}. \end{enumerate} The amazing thing about this device is that it is able to perform \textbf{50 000} operations of this kind with a sequence of \textbf{50 000} numbers within \textbf{3} seconds. Nobody could do it before! But Roman does not believe in aliens and thinks that it is only a great hoax made by somebody just to win another million bucks on the stock exchange. His goal is to prove this. So he hired you to write a program to simulate this device. Given an integer sequence \textbf{a_i} and a sequence of operations, write a program which simulates the behaviour of the strange alien device. \InputFile The first line of the input contains the length of the sequence \textbf{ n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50 000}). The second line contains \textbf{n} numbers ai forming the initial sequence (\textbf{0} ≤ \textbf{a_i} ≤ \textbf{2009}). The third line contains the number of operations \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{50 000}). The rest of file contains \textbf{m} lines, each describing one operation. The \textbf{j}-th operation is described by its kind \textbf{k_j} ('\textbf{1}' for squaring, '\textbf{2}' for calculating the sum), followed by two integers \textbf{l_j} and \textbf{r_j} (\textbf{1} ≤ \textbf{l_j} ≤ \textbf{r_j} ≤ \textbf{n}). \OutputFile For each operation of the second kind, write their output on the separate line, in order they appear in the input.
Time limit 1 second
Memory limit 256 MiB
Input example #1
3
17 239 999
4
2 1 3
1 2 3
2 2 3
2 1 2
Output example #1
1255
1882
858
Author R.Satukov, A.Lopatin
Source ACM ICPC 2009-2010, NEERC, Northern Subregional Contest, St Petersburg, October 17, 2009