You are given an array of non-negative integers of length $n$. You have to perform two types of operations on them.

Type-1:$L$$R$. Convert all the numbers from index $L$ to $R$ to their binary. Perform a cyclic left-shift on the binary representations of the numbers. Then convert them back to decimal again.

Type-2:$L$$R$. Print the sum of all the integers from $L$ to $R$.

Input

First line contains two space separated integers $n$ and $q$, where $n$ is the size of given array and $q$ is the number of operations you have to perform.

Second line contains $n$ space separated integers.

Each of the next $q$ lines contain $3$ integers describing the operations in the following format. type $L$$R$

Constraints $1 \le n \le 2\cdot10^{5}$ $1 \le q \le 2\cdot10^{5}$ $1 \le type \le 2$ $1 \leq L \leq R \leq N$ $A_i$ fits in a 32-bit signed integer.

Output

For each Type-2 operation, print an integer $S$ which is the sum of integers from index $L$ to $R$.

Sample

Input

Output

5 5
4 5 13 6 0
1 1 3
2 1 5
1 2 5
1 1 5
2 1 5

21
14

Description about Type-1 operation: Suppose you want to perform the circular left shift on 57. Here's the total process:

Convert 57 to binary. (57)10 = (111001) 2

Perform circular left shift: (111001) 2 becomes (110011) 2