수수께끼의 장치

어떤 신기한 장치가 정수 수열 $a_1, a_2, \ldots, a_n$ 을 저장하고 반복해서 변형한다. 이 장치는 두 종류의 연산을 지원한다.

1. 제곱 — 구간 $[l, r]$ 이 주어지면, $l \le i \le r$ 인 모든 $i$ 에 대해 $a_i \leftarrow a_i^2 \bmod 2010$ 으로 바꾼다.
2. 합 — 구간 $[l, r]$ 이 주어지면, $\sum_{i=l}^{r} a_i$ 를 출력한다. 이 합은 2010으로 나눈 나머지를 취하지 않는다.

장치의 동작을 그대로 흉내 내어, 각 제곱 연산을 수행하고 각 합 질의에 답하라.

첫째 줄에 수열의 길이 $n$ 이 주어진다 ($1 \le n \le 50,000$).

둘째 줄에 초기 수열을 이루는 $n$ 개의 정수 $a_1, \ldots, a_n$ 이 주어진다 ($0 \le a_i \le 2009$).

셋째 줄에 연산의 개수 $m$ 이 주어진다 ($1 \le m \le 50,000$).

이어지는 $m$ 개의 줄에는 각각 하나의 연산이 세 정수 $k$, $l$, $r$ 로 주어진다. $k = 1$ 이면 구간을 제곱하고, $k = 2$ 이면 구간의 합을 질의하며, $1 \le l \le r \le n$ 이다.

두 번째 종류의 연산마다, 입력에 나타난 순서대로 그 결과를 한 줄에 하나씩 출력한다.