题目描述

这一天终于到来了：人类与外星文明建立了第一次接触。外星人承诺带来一种以地球现有技术无法制造的神秘装置。

该装置首先接收一个整数序列 $a_1,a_2,\ldots,a_n$，之后支持以下两种操作：

1. 给定区间 $[l,r]$，对其中每个元素执行

   $$a_i\leftarrow a_i^2\bmod 2010 \qquad (l\le i\le r).$$

2. 给定区间 $[l,r]$，输出

   $$\sum_{i=l}^{r} a_i.$$

   注意，这个和不对 $2010$ 取模。

据说，这台装置能够在 3 秒内处理长度为 $50\,000$ 的序列以及 $50\,000$ 次操作。Roman 不相信这是外星科技，希望你编写程序模拟它的行为。

输入格式

第一行包含一个整数 $n$，表示序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始序列。

第三行包含一个整数 $m$，表示操作数量。

接下来 $m$ 行，每行包含三个整数 $k,l,r$：

• 当 $k=1$ 时，对区间 $[l,r]$ 中的所有元素执行一次平方并对 $2010$ 取模；
• 当 $k=2$ 时，询问区间 $[l,r]$ 的元素和。

输出格式

对于每个第二类操作，单独输出一行，表示对应区间的元素和。

数据范围

• $1\le n\le 50\,000$；
• $0\le a_i\le 2009$；
• $1\le m\le 50\,000$；
• $1\le l\le r\le n$。

样例

输入

3
17 239 999
4
2 1 3
1 2 3
2 2 3
2 1 2

输出

1255
1882
858