Background

我出的题肯定水！

Description

给定一个序列\(a_0\),\(a_1\),...\(a_{n-1}\)
给定m个询问和修改操作，操作包含\(i,l,r\)
\(i=0\)为修改操作，代表将区间\([l,r]\)之间的数字开根号向下取整
\(i=1\)为查询操作，代表查询区间\([l,r]\)的数字和
数据范围\(0<n,m<=1e5,a_i>=0,0<=l<=r<n,\sum{a_i}\)在long long范围内
单个ai的值不超过int

Format

Input

第一行一个数字\(n\)
第二行\(n\)个数字，包含\(a_0...a_{n-1}\)
第三行一个数字m，代表操作个数
接下来\(m\)行，每行三个数字\(i,l,r\)。

Output

对于每个询问，输出一个答案，答案对\(1e9+7\)取模

Sample 1

Input

3
9 9 9
1
1 0 2

Output

27

Limitation

1s, 64*1024KiB for each test case.

Source

Vijos Original