Today, Rikka is going to learn how to use BIT to solve some simple data structure tasks. While studying, She finds there is a magic expression in the template of BIT. After searching for some literature, Rikka realizes it is the implementation of the function .

is defined on all positive integers. Let a₁...a_m be the binary representation of x while a₁ is the least significant digit, k be the smallest index which satisfies a_k = 1. The value of is equal to 2^k-1.

After getting some interesting properties of , Rikka sets a simple data structure task for you:

At first, Rikka defines an operator f(x), it takes a non-negative integer x. If x is equal to 0, it will return 0. Otherwise it will return or , each with the probability of .

Then, Rikka shows a positive integer array A of length n, and she makes m operations on it.

There are two types of operations:
1. 1 L R, for each index i ∈ [L,R], change A_i to f(A_i).
2. 2 L R, query for the expectation value of . (You may assume that each time Rikka calls f, the random variable used by f is independent with others.)

The first line contains a single integer t(1 ≤ t ≤ 3), the number of the testcases.

The first line of each testcase contains two integers n,m(1 ≤ n,m ≤ 105). The second line contains n integers Ai(1 ≤ Ai ≤ 108). 

And then m lines follow, each line contains three integers t,L,R(t ∈ {1,2}, 1 ≤ L ≤ R ≤ n).

For each query, let w be the expectation value of the interval sum, you need to output . 

It is easy to find that w x 2nm must be an integer.

1
3 6
1 2 3
1 3 3
2 1 3
1 3 3
2 1 3
1 1 3
2 1 3

1572864
1572864
1572864