P12827 「DLESS-2」XOR and Even

You are given a sequence $a$ of $n$ non-negative integers. You need to process $q$ queries, each being one of the following two types: - ```0 l r x```: Count the number of ways to select an **even** number of elements from the range $[l, r]$ (inclusive) such that their XOR sum is less than or equal to $x$. Selecting zero elements is allowed, and their XOR sum is $0$. Output the count modulo $10^9+7$. - ```1 l r x```: Select an **even** number of elements from the range $[l, r]$ (inclusive). Let their XOR sum be $S$. Find the maximum possible value of $S \oplus x$.

This problem contains multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case: The first line contains two integers, $n$ and $q$. The second line contains $n$ integers, representing the sequence $a$. Each of the next $q$ lines describes a query in the format specified in the problem description.

For each query, output a single integer on one line, representing the answer.

For all test cases, it is guaranteed that: - $1\le T\le 10^4$ - $1\le n,\sum n\le 5\times10^5$ - $1\le q,\sum q\le 5\times10^5$ - $1\le l