# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Going Round in Circles

By souravvv · Limits 2s, 512 MB

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

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

21
14


Suppose you want to perform the circular left shift on 57. Here's the total process:

1. Convert 57 to binary. (57)10 = (111001) 2
2. Perform circular left shift: (111001) 2 becomes (110011) 2
3. Convert back to decimal: (110011)2=(51)10
• FenwickTree

### Statistics

92% Solution Ratio

serotoninEarliest, Jul '20

Alomgir27Fastest, 0.1s

prodip_bsmrstuLightest, 8.9 MB

Zobayer_AbedinShortest, 1128B

### Submit 