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 nn. You have to perform two types of operations on them.

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

Type-2: LL RR. Print the sum of all the integers from LL to RR.

Input

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

Second line contains nn space separated integers.

Each of the next qq lines contain 33 integers describing the operations in the following format.
type LL RR

Constraints
1n21051 \le n \le 2\cdot10^{5}
1q21051 \le q \le 2\cdot10^{5}
1type21 \le type \le 2
1LRN1 \leq L \leq R \leq N
AiA_i fits in a 32-bit signed integer.

Output

For each Type-2 operation, print an integer SS which is the sum of integers from index LL to RR.

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


92% Solution Ratio

serotoninEarliest, Jul '20

Alomgir27Fastest, 0.1s

prodip_bsmrstuLightest, 8.9 MB

Zobayer_AbedinShortest, 1128B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.