题目描述

给定一个长度为 n 的数列和 n 个涉及区间开方和区间求和的操作。

输入

• 第一行包含一个整数 n。

• 第二行包含 n 个整数，其中第 i 个整数表示为 a_i，用空格分隔。

• 接下来的 n 行表示查询。每行包含四个整数 opt、l、r 和 c，用空格分隔。

  如果 opt = 0，表示将位于 [l, r] 区间的所有数字都开方。对于区间中每个 a_i (l ≤ i ≤ r)，a_i 变为 $\lfloor\sqrt{a_i}\rfloor$。

  如果 opt = 1，表示查询位于 [l, r] 区间的所有数字的和。

输出

对于每次查询，输出一行包含一个整数，表示答案。

样例

输入

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

输出

6
2

限制

对于100%的数据，1 ≤ n ≤ 50000，且0 ≤ others, ans ≤ 2^31-1。