CF2096H.Wonderful XOR Problem

你是...算了，直接解决这个问题吧。

有 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$。对于每个 $x$ 从 $0$ 到 $2^m - 1$，求满足以下条件的序列 $a_1, a_2, \ldots a_n$ 的数量（模 $998\,244\,353$）：

• 对于所有 $i$ 从 $1$ 到 $n$，有 $l_i \leq a_i \leq r_i$；
• $a_1 \oplus a_2 \oplus \ldots \oplus a_n = x$，其中 $\oplus$ 表示按位异或运算符。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq 18$）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \leq l_i \leq r_i < 2^m$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且所有测试用例的 $2^m$ 之和不超过 $2^{18}$。

对于每个 $x$ 从 $0$ 到 $2^m - 1$，定义：

• $f_x$ 为有效序列的数量，模 $998\,244\,353$；
• $g_x = f_x \cdot 2^x \mod 998\,244\,353$。

这里，$f_x$ 和 $g_x$ 都是区间 $[0, 998\,244\,352]$ 内的整数。

设 $h = g_0 \oplus g_1 \oplus \ldots \oplus g_{2^m - 1}$。

输出一个整数——$h$ 的值本身。不要进行模运算。

对于第一个测试用例，$f_x$ 的值如下：

• $f_0 = 2$，因为有 $2$ 个有效序列：$[1, 1]$ 和 $[2, 2]$；
• $f_1 = 2$，因为有 $2$ 个有效序列：$[0, 1]$ 和 $[2, 3]$；
• $f_2 = 2$，因为有 $2$ 个有效序列：$[0, 2]$ 和 $[1, 3]$；
• $f_3 = 3$，因为有 $3$ 个有效序列：$[0, 3]$、$[1, 2]$ 和 $[2, 1]$。

$g_x$ 的值如下：

• $g_0 = f_0 \cdot 2^0 = 2 \cdot 2^0 = 2$；
• $g_1 = f_1 \cdot 2^1 = 2 \cdot 2^1 = 4$；
• $g_2 = f_2 \cdot 2^2 = 2 \cdot 2^2 = 8$；
• $g_3 = f_3 \cdot 2^3 = 3 \cdot 2^3 = 24$。

因此，输出的值为 $2 \oplus 4 \oplus 8 \oplus 24 = 22$。

对于第二个测试用例，$f_x$ 的值如下：

• $f_{0} = 120$；
• $f_{1} = 120$；
• $f_{2} = 119$；
• $f_{3} = 118$；
• $f_{4} = 105$；
• $f_{5} = 105$；
• $f_{6} = 106$；
• $f_{7} = 107$。

翻译由 DeepSeek V3 完成