题目描述

给定正整数 $n, m$ 和 $n$ 个区间，第 $i$ 个区间为 $[l _ i, r _ i]$，保证 $0 \leq l_i \leq r_i < 2^m$。

对于非负整数 $x$，记 $S _ m(x)$ 表示 $x$ 在二进制下最低的 $m$ 位依次连接成的 01 串，如果不足 $m$ 位则在高位补 $0$。

对于 $k = 1, 2, \cdots ,n$，求有多少非负整数序列 $a _ 1, a _ 2, \cdots, a _ k$ 满足下列条件。

• 对于所有 $1 \leq i \leq k$，$l _ i \leq a _ i \leq r _ i$。
• $S _ m(a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ k)$ 是回文串，其中 $\oplus$ 表示按位异或运算。

答案对 $998244353$ 取模。

输入格式

输入共 $n + 1$ 行。

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

接下来 $n$ 行，每行两个非负整数 $l _ i, r _ i$，表示第 $i$ 号区间是 $[l _ i, r _ i]$。

输出格式

共 $n$ 行，第 $i$ 行有一个非负整数，表示当 $k = i$ 时的答案。

4 2
1 3
2 3
0 0
1 2

1
3
3
6

以 $k = n$ 时为例，满足题目所述条件的 $6$ 个序列分别为 $[1, 3, 0, 1]$、$[1, 3, 0, 2]$、$[2, 3, 0, 1]$、$[2, 3, 0, 2]$、$[3, 2, 0, 1]$、$[3, 2, 0, 2]$。

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

2
9 
45
90
180

数据范围与提示

对于所有数据，满足 $1 \le n \le 40, 1 \le m \le 60, 0 \le l _ i \le r _ i < 2 ^ m$。

共 $25$ 个测试点，每个测试点 $4$ 分，具体测试点范围见下表。