You are given an array of non-negative integers of length n. You have to perform two types of operations on them.
Type-1: LR. 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: LR. Print the sum of all the integers from L to R.
Input
First line contains two space separated integers n (1≤n≤2⋅105) and q (1≤q≤2⋅105), 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
1≤type≤2,1≤L≤R≤N, Ai 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