Xor

• 时间限制：2s
• 空间限制：1024MB

题目描述

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

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

输入格式

第一行包含两个整数 $n$ 和 $m$。

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

输出格式

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

• $f_x$ 为有效序列的数量，模 $998244353$；
• $g_x = f_x \cdot 2^x \bmod 998244353$。

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

设：

$$h = g_0 \oplus g_1 \oplus \cdots \oplus g_{2^m-1}.$$

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

输入输出样例

2 2
0 2
1 3

22

5 3
3 7
1 3
0 2
1 5
3 6

9812

10 14
314 1592
653 5897
932 3846
264 3383
279 5028
841 9716
939 9375
105 8209
749 4459
230 7816

75032210

1 5
0 29

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

数据范围

子任务	$n \le$	$m \le$	特殊性质	分数
1	$100$	$9$		5
2		$15$		15
3	$2 \times 10^5$	$18$	$l_i=1,\, r_i=2^k-1\ (k=1,2,\dots,18)$	10
4	$4000$	$15$		20
5	$2 \times 10^5$
6		$18$		30