你是骄傲...没关系,解决这个问题就可以了。
有 $$$n$$$ 间隔 $$$[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$$$。对于从 $$$0$$$ 到 $$$2^m - 1$$$ 的每个 $$$x$$$,找到序列 $$$a_1, a_2, \ldots a_n$$$ 的模数 $$$998\,244\,353$$$,使得:
- $$$l_i \leq a_i \leq r_i$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$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 \lt 2^m$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$2^m$$$总和不超过$$$2^{18}$$$。
输出
对于从 $$$0$$$ 到 $$$2^m - 1$$$ 的每个 $$$x$$$,让:
- $$$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$$$ 本身的值。 不 执行模运算。
示例
输入复制
42 20 21 35 33 71 30 21 53 610 14314 1592653 5897932 3846264 3383279 5028841 9716939 9375105 8209749 4459230 78161 50 29
输出复制
22 9812 75032210 1073741823
注意
对于第一个测试用例,$$$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$$$。