Sequence Modification and Query

You are given a sequence of n positive integers. There will be q operations on this sequence. There are two types of operations:

• Type 1 (Modification): For a given range [L, R], replace each element a[i] with \( \lfloor\sqrt{a[i]}\rfloor \). That is, set \( a[i] = \lfloor\sqrt{a[i]}\rfloor \) for all L \( \le i \le R \).
• Type 2 (Query): For a given range [L, R], output the sum of a[L] + a[L+1] + ... + a[R].

The input is designed with NOIP-level difficulty, so the data range is large. However, it is guaranteed that during all operations and at the end the intermediate and final results will not exceed the 64-bit signed integer range \( [-2^{63}, 2^{63}-1] \).

Note: Once an element becomes 1, further modification on that element will keep it unchanged, since \( \lfloor\sqrt{1}\rfloor = 1 \).

You are tasked to process the operations and output the answer for each query operation.

inputFormat

The first line contains two integers n and q, which represent the number of elements in the sequence and the number of operations, respectively.

The second line contains n positive integers, representing the initial sequence.

Each of the following q lines describes an operation in the format:

• If the operation is a modification, the line contains: 1 L R.
• If the operation is a query, the line contains: 2 L R.

Here, L and R are 1-indexed positions.

outputFormat

For each query operation (operation type 2), output a single line containing the sum of the specified subarray.

sample

5 5
4 16 20 1 9
2 1 5
1 2 4
2 1 5
1 1 5
2 1 3

50
22
6