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

Description about Type-1 operation:
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

    Discussion

    Statistics


    88% Solution Ratio

    serotoninEarliest, 2w ago

    prodip_bsmrstuFastest, 0.1s

    prodip_bsmrstuLightest, 8.9 MB

    serotoninShortest, 1230B

    Submit

    Login to submit