A134851.游戏

Steve 和 Alice 在玩一个游戏。两个人各自选择一个长度为 $n$ 的正整数序列 $s,t$，满足 $s_i,t_i\le d$ 且要求 $s\not= t$。初始时有一个空序列 $S$，两人重复以下过程直到某个人获胜：

• 等概率地在 $[1,d]$ 之间选择一个整数，将其加入到序列 $S$ 的末尾；
• 若此时 $s$ 是 $S$ 的后缀，则 Steve 直接获胜；若此时 $t$ 是 $S$ 的后缀，则 Alice 直接获胜；否则继续重复这个过程。

可以证明游戏结束的概率为 $1$。

该问题分为两个部分，分别对应子问题一或者子问题二。你可以按任意顺序解决这些子问题。特别地，你无需先完成子问题一再尝试子问题二。

• 子问题一（$80$ 分）：给出 Steve 和 Alice 选择的序列 $s,t$，你需要求出 Steve 获胜的概率，对 $998244353$ 取模，保证答案在模 $998244353$ 意义下存在。
• 子问题二（$20$ 分）：给出 Alice 选择的序列 $t$，你需要帮 Steve 选择一个合法的序列 $s$，满足 $s\not=t$ 且 Steve 获胜的概率大于 $\dfrac12$。可以证明，在题目的限制条件下，这样的 $s$ 总是存在。

如果你不知道怎么计算一个分数对质数取模后的结果，可以参考 洛谷 P3811 【模板】模意义下的乘法逆元。

每个测试点包含多组测试数据。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数，对于每组测试数据：

• 若 $1\le c\le 8$，第一行包含两个正整数 $n,d$，分别表示序列的长度和元素的上界；第二行包含 $n$ 个正整数 $s_1,s_2,\dots,s_n$，表示 Steve 选择的序列；第三行包含 $n$ 个正整数 $t_1,t_2,\dots,t_n$，表示 Alice 选择的序列；
• 若 $9\le c\le 10$，第一行包含两个正整数 $n,d$，分别表示序列的长度和元素的上界；第二行包含 $n$ 个正整数 $t_1,t_2,\dots,t_n$，表示 Alice 选择的序列。

本题采用 Special Judge，对于子任务二，你只需要构造出任意一种符合条件的序列。

对于每组测试数据：

• 若 $1\le c\le 8$，输出一行一个整数，表示 Steve 获胜的概率对 $998244353$ 取模后的结果；
• 若 $9\le c\le 10$，输出一行 $n$ 个整数 $s_1,s_2,\dots,s_n$，表示你帮 Steve 选择的序列。

测试点编号	特殊性质
$1$	$n=3,d=2$
$2-4$	$T\le 10,n\le 100,d=2$
$5-6$	$d=2$
$7-8$	无
$9$	$t_i=1$
$10$	无

对于 $100\%$ 的测试点：

• 若 $1\le c\le 8$，保证：$1\le T\le10^4$，$3\le n\le 2\times 10^5$，$2\le d\le 2\times 10^5$，$1\le s_i,t_i\le d$，$s\not=t$，单个测试点中所有测试数据的 $n$ 之和不超过 $2\times 10^5$。
• 若 $9\le c\le 10$，保证：$1\le T\le10^4$，$3\le n\le 2\times 10^5$，$2\le d\le 2\times 10^5$，$1\le t_i\le d$，单个测试点中所有测试数据的 $n$ 之和不超过 $2\times 10^5$。