题目背景

在一片神秘的数据结构大陆上，造物之神用了七分钟创造了这个世界。

第一分钟，他掷下了序列；第二分钟，他赐予了开方的神力；第三分钟，他允许了求和的祈祷；第四分钟，他定下了数据的边界；第五分钟，他施加了时间与空间的枷锁；第六分钟，他保证了运算不会溢出；第七分钟，他合上了书卷，将一切交给了解题者。

题目描述

给定一个由 $n$ 个正整数构成的数列 $a_1, a_2, \ldots, a_n$。

现在有 $m$ 次操作，操作分为两种：

• 0 l r：将 $a_l, a_{l+1}, \ldots, a_r$ 中的每个数替换为其算术平方根向下取整的值。
• 1 l r：查询 $a_l + a_{l+1} + \ldots + a_r$ 的值。

注意：输入数据中 $l$ 可能大于 $r$，遇到这种情况请先交换 $l$ 和 $r$。

保证运算过程中及最终结果均不超过 $64$ 位有符号整数类型的表示范围。

输入格式

第一行一个整数 $n$，表示数列中数的个数。

第二行 $n$ 个正整数，表示初始状态下数列中的数。

第三行一个整数 $m$，表示有 $m$ 次操作。

接下来 $m$ 行，每行三个整数 k l r，描述一次操作。

输出格式

对于每次询问操作（$k=1$），输出一行一个整数，表示区间和。

样例

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

19
7
6

提示

对于 $30\%$ 的数据，$1 \le n,m \le 10^3$，数列中的数不超过 $32767$。

对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$1 \le l,r \le n$，数列中的数大于 $0$，且不超过 $10^{12}$。