Sherlock Holmes has helped the London Police to solve a lot of cases and sent a lot of criminals to prison. But now he is getting bored as there is no interesting case to solve. So he decides to play a game with Watson to spend his time.

Initially he gives him an array of N numbers A₁, A₂, A₃, … A_n. Now, he asks Watson to tell him the sum of the squares of all numbers in any subarray from A_i to A_j.

i.e. A_i² + A_i+1² + ...+ A_j².

To increase the difficulty of the task, he updates the numbers in any subarray from A_i to A_j from time to time. The update is performed in two steps-

1) He multiplies all numbers in the subarray by 2.

2) He divides all multiples of 2048 in the subarray by 2048.

Dr. Watson knows that if he is unable to answer Sherlock’s queries, Sherlock will boast about it for days. So he asks for your help to keep Sherlock’s ego under control.

Input

The first line contains T, the number of test cases.

For each test case, the first line of input contains 2 integers N and Q(number of queries).

Next line contains N integer A₁, A₂, A₃, … A_n.
Next Q lines contain each defines a query-

0 i j - Sherlock updates all the numbers in the subarray from A_i to A_j as defined above.

1 i j - Watson needs to tell the sum of squares of all numbers in the subarray from A_i to A_j.

Output

For each query of the form 1 i j, output 1 line containing the answer to Sherlock's problem.

Constraints

T

1

1

1

Example

Input: 2 4 3 5 2 1 6 1 2 3 0 1 3 1 2 4 1 3 512 0 1 1 0 1 1 1 1 1 Output: 5 56 1