Description

小图有一个长度长度为 $n$ 的数组 $a$，和 $m$ 次操作，每次操作形如 $op ,x, y$。

$op = 1:$ 对 $a_x$ 到 $a_y$ 内每个元素开方后下取整。即 $a_i = \lfloor \sqrt{a_i} \rfloor,x \le i \le y$。 $op = 2:$ 查询 $a_x$ 到 $a_y$ 内元素的和。

Format

Input

第一行两个正整数 $n,m(1 \leq n,q \leq 3\times10^5)$。 第二行 $n$ 个整数 $a_1,a_2,\dots, a_n(1 \le a_i \le 10^9)$。 接下来 $m$ 行，每行形如 $op \quad x \quad y(op \in \{1,2\}, 1 \le x \le y \le n)$。

Output

对每个操作 $2$，输出一行一个整数。

Samples

5 5
1 2 3 4 5
1 1 2
2 1 3
1 3 5
1 2 4
2 1 5

5 
6