题目描述

3202 年，科研人员发现了一颗超级地球：$\lambda$ 星。

$\lambda$ 星有 $n$ 座山，第 $i$ 座山高度为 $a_i$，保证所有 $a_i\in[1,n]$ 且两两不同。科考队会兵分多路，同时前往若干座山（也可以一座都不前往）进行考察。

• 称第 $x$ 与第 $y$ 座山“相邻”，当且仅当所有坐落在其间的山都比这两座山低。
• 两名科考人员“可直接通讯”，当且仅当他们位于同一座山，或他们位于的山相邻。
• 两名科考人员“可通讯”，当且仅当存在一条经过若干科考人员的路径 $p_1\to p_2\to\cdots\to p_k$，满足 $p_1$ 为小 A，$p_k$ 为小 B，且对所有 $i\in[1,k)$，$p_i$ 与 $p_{i+1}$ 可直接通讯。

我们称一种“考察方案”（选择若干座山去考察）是合法的，当且仅当任意两名科考队员都可通讯。
两种方案不同，当且仅当存在一座山在一种方案中被考察，而在另一种方案中未被考察。

可惜我们并不知道 $n$ 及 $a_1,\dots,a_n$。为此：
对于所有 $n\in[1,N]$，你需要对所有长度为 $n$ 的排列 $a$，求出合法考察方案数的总和对 $998244353$ 取模的值，记为 $\mathrm{ans}_n$。

为降低输入/输出量，本题输入输出方式较特殊，见下文。

输入格式

• 第一行两个正整数 $T, N$。
• 接下来 $T$ 行，每行两个正整数 $l,r$，描述一次查询。

输出格式

对每次查询输出一行：表示 $\mathrm{ans}_l,\mathrm{ans}_{l+1},\dots,\mathrm{ans}_r$ 的异或和。

6 500000
1 5
1 10
1 300
1 5000
1 100000
1 500000

2125
883527685
637022794
1028511112
584326960
536722215

样例解释（节选）

第一个查询中，$\mathrm{ans}_1,\mathrm{ans}_2,\mathrm{ans}_3,\mathrm{ans}_4,\mathrm{ans}_5$ 的值分别为 $1,6,38,280,2420$，其异或和为 2125。

数据范围与提示

本题采用捆绑测试。

• Subtask 1（5pts）：$N \le 5$
• Subtask 2（5pts）：$N \le 10$
• Subtask 3（10pts）：$N \le 300$
• Subtask 4（30pts）：$N \le 5000$
• Subtask 5（30pts）：$N \le 10^5$
• Subtask 6（20pts）：无特殊限制

对 100% 数据满足：

• $1 \le T \le 10^4$
• $1 \le N \le 5\times 10^5$
• $1 \le l \le r \le N$

请注意常数因子对程序运行效率的影响。