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 (1n21051 \le n \le 2\cdot10^{5}) and qq (1q21051 \le q \le 2\cdot10^{5}), 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 3 integers describing the operations in the following format.

type L R

1type21 \le \texttt{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(57)_{10} = (111001)_2
  2. Perform circular left shift: (111001)2(111001)_2 becomes (110011)2(110011)_2
  3. Convert back to decimal: (110011)2=(51)10(110011)_2 = (51)_{10}

Submit

Login to submit.

Contributors

Statistics

96% Solution Ratio
serotoninEarliest, Jul '20
Alomgir27Fastest, 0.1s
prodip_bsmrstuLightest, 8.9 MB
Zobayer_AbedinShortest, 1128B
Toph uses cookies. By continuing you agree to our Cookie Policy.