给定序列A[1], A[2], A[3], ..., A[N]。
现在要对它进行M次操作，每次可进行如下两种操作：
0. 给定(x, y)，对A[x], A[x+1], ..., A[y]这些数字开根号，向下取整。
1. 给定(x, y)，对区间[x, y]进行求和，即求\sum_{i=x}^{y}A[i]。

第一行输入一个整数N。
第二有N个正整数A[1], A[2], A[3], ..., A[N]。
接下来给出一个整数M。
接下来M行，每行三个整数i, x, y。
当i = 0时，执行第0种操作，否则执行第1种操作。

输入保证1 \le N \le 10^5，1 \le M \le 10^5，A[i] \ge 1， \sum_{i=1}^{N}A[i]\le 10^{18}，1 \le x \le y \le N

对于第1种操作，输出区间和。