D. Magical Flower Garden
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ananya is the owner of a magical flower garden. The garden contains $$$n$$$ flowers in a line numbered left to right from $$$1$$$ to $$$n$$$. Each flower has a color that can be represented by a non-negative integer. The garden can be represented as an array $$$A$$$ of length $$$n$$$, where $$$A_i$$$ denotes the color of the $$$i$$$-th flower from the left.

The saturation of a color $$$a$$$ is defined as $$$\operatorname{popcount}(a)$$$, which is the number of $$$1$$$s in the binary representation of $$$a$$$. For example, the saturation of color $$$14$$$ is $$$3$$$ since the binary representation of $$$14$$$ is $$$1110$$$, which contains three $$$1$$$s. To change the color of a flower, Ananya can sprinkle magical dust on it. Sprinkling magical dust with value $$$b$$$ on a flower changes its color from $$$a$$$ to $$$a | b$$$, where $$$|$$$ denotes the bitwise OR operation.

Ananya loves her garden and wants to keep it beautiful. She defines the beauty of the garden as the sum of scores of all its subarrays. The score of a subarray is defined as the product of its length and the maximum saturation among the colors of the flowers in that subarray.

Formally, the score of the subarray $$$A[l \dots r]$$$, $$$$$$ \operatorname{score}(A[l \dots r]) = (r - l + 1) \cdot \max_{l \le i \le r} \operatorname{popcount}(A_i) $$$$$$

The beauty of the array $$$A$$$, $$$$$$ \text{beauty}(A) = \sum_{l=1}^{n} \sum_{r=l}^{n} \operatorname{score}(A[l \dots r]) $$$$$$

As your team is participating in the ICPC this year and is known as excellent problem solvers, Ananya has appointed you as the caretaker of her garden. Everyday, she gives you exactly one task to perform on her flowers. The tasks can be of one of the following two types:

  • Type 1: She gives you two numbers $$$p$$$ and $$$q$$$ $$$(0 \le p \le 30, 1 \le q \le 10^9)$$$. You have to find the flower whose saturation is exactly $$$p$$$ and sprinkle magical dust with value $$$q$$$ on it. If the garden currently contains multiple flowers with saturation $$$p$$$, pick the leftmost one. If there's currently no flower with saturation $$$p$$$, do nothing. Formally, find the smallest index $$$i$$$ such that $$$\operatorname{popcount}(A_i) = p$$$ and if such an $$$i$$$ exists, perform, $$$A_i := A_i | q$$$.

  • Type 2: She wants to know how beautiful the garden is. You have to output the current beauty of the garden.

Your goal is to perform each daily task carefully.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$d$$$ $$$(1 \le n, d \le 10^5)$$$ — the number of flowers in the garden and the number of days respectively.

The second line of each test case contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$ $$$(0 \le A_i \le 10^9)$$$ — the initial colors of the flowers.

Each of the next $$$d$$$ lines represents the task for a particular day, given sequentially. The tasks can be of one of the following two formats:

  • "1 p q": Find the leftmost flower whose current saturation is equal to $$$p$$$ and if such a flower exists, sprinkle magical dust with value $$$q$$$ on it.
  • "2": Output the current beauty of the garden.

It is guaranteed that the sum of $$$(n + d)$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. It is also guaranteed that each test case contains at least one task of type $$$2$$$.

Output

For each task of type $$$2$$$, print a single integer in a line — the current beauty of the garden.

Example
Input
2
3 5
2 1 3
2
1 2 4
2
1 1 1
2
9 6
8 3 4 6 1 7 3 8 2
2
1 2 5
2
1 2 6
1 3 8
2
Output
16
22
25
443
467
547
Note

The following diagram illustrates the initial state of the garden for the first sample test case, along with the scores of each subarray:

The initial beauty of the garden is $$$1 + 1 + 2 + 2 + 4 + 6 = 16$$$.