题目描述

给定一个长度为 $n$ 的非负整数序列 $a$，$q$ 次询问，每次询问形如以下两种中的一种：

• 0 l r x: 在区间 $[l,r]$ 中选出偶数个数（可以是 $0$ 个，此时异或和为 $0$，下同），使得这些数的异或和小于等于 $x$，求方案数，答案对 $10^9+7$ 取模。
• 1 l r x: 在区间 $[l,r]$ 中选出偶数个数，使得这些数的异或和异或上 $x$ 最大，求这个最大值。

输入格式

本题有多组测试数据，第一行输入一个数 $T$ 表示数据组数。

对于每组数据，第一行输入两个数 $n,q$。

第二行输入 $n$ 个数，代表序列 $a$。

接下来 $q$ 行，每行一次询问，格式如问题描述所示。

输出格式

对于每次询问，输出一行一个数，表示答案。

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

提示

对于所有数据，保证：

• $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}$

本题采用捆绑测试，各子任务描述如下：

特殊性质 A：操作类型一定为 $0$。

特殊性质 B：操作类型一定为 $1$。