Problem Description

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$.

Input Format

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.

Output Format

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

2
5 6
1 2 4 8 16
0 1 3 3
0 1 4 3
1 2 4 0
1 2 4 1
0 1 5 114514
0 1 4 5
6 7
1 1 4 5 1 4
0 1 3 0
1 2 4 0
1 1 2 1
1 2 6 0
1 1 4 5
0 2 4 4
1 1 2 0

2
2
12
13
16
3
2
5
1
5
5
3
0

Hint

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<r\le n$
• $0\le a_i,x<2^{30}$

This problem uses subtasks for scoring (bundled testing). The descriptions of the subtasks are as follows:

Special Property A: All queries are of type 0.

Special Property B: All queries are of type 1.