Enigmatic Device

A curious device stores an integer sequence $a_1, a_2, \ldots, a_n$ and repeatedly transforms it. It supports two kinds of operations:

1. Square — given an interval $[l, r]$, replace $a_i \leftarrow a_i^2 \bmod 2010$ for every index $i$ with $l \le i \le r$.
2. Sum — given an interval $[l, r]$, output $\sum_{i=l}^{r} a_i$. This running sum is not reduced modulo 2010.

Simulate the device: apply each squaring operation and answer each sum query.

The first line contains the sequence length $n$ ($1 \le n \le 50\,000$).

The second line contains $n$ integers $a_1, \ldots, a_n$, the initial sequence ($0 \le a_i \le 2009$).

The third line contains the number of operations $m$ ($1 \le m \le 50\,000$).

Each of the next $m$ lines describes one operation with three integers $k$, $l$, $r$: $k = 1$ squares the interval, $k = 2$ queries its sum, and $1 \le l \le r \le n$.

For each operation of the second kind, print its result on its own line, in the order the queries appear in the input.