A7466 | 游戏

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 选择的序列。