[yLOI2020] 灼

题目背景

> 声嘶力竭,向悲泣的虚空祈祷至最后, > 神为何依然残酷冷漠。 > 天国或地狱,也奢求你无垢眼眸, > 就让我,再次被你拯救。 ——银临《灼》

题目描述

> 这里是 NS05,勒本星球已无生命反应,请求救援!普尔!——你听得到吗?我会一直在这里,等待你的归来。 扶苏被困在了勒本星球,灼闻羽驾驶着一架宇宙飞船正打算穿越虫洞到达勒本星球拯救扶苏。 在一条数轴上有 $n$ 个虫洞,第 $i$ 个虫洞的坐标为 $x_i$。进入这些虫洞的任意一个都可以直接到达勒本星球拯救扶苏。飞船到达数轴所在直线上后,会因为磁场的效应失去操控能力,飞船每秒会**等概率**向左或向右移动一个单位长度。 灼闻羽非常焦急,他给出了 $q$ 个飞船进入数轴所在直线的初始坐标,对于每个坐标,他想知道期望需要多少秒才能到达一个虫洞。 如果你计算出的期望是个分数,你需要求出这个分数对 $998244353$ 取模的答案。有关分数取模的定义你可以参考「提示」中的内容。 为了避免输出过大,你只需要输出四个整数,分别表示你所有回答(对 $998244353$ 取模之后,下同)的按位异或之和、你共有多少次回答的答案是奇数,你的所有答案中的最大值、你的所有答案中的最小值。

输入输出格式

输入格式


第一行是一个整数,表示测试点所对应的编号 $T$。 第二行有两个整数,分别表示虫洞的个数 $n$ 和初始坐标的个数 $q$。 第三行有 $n$ 个整数,第 $i$ 个整数表示第 $i$ 个虫洞的坐标 $x_i$。 接下来 $q$ 行,每行一个整数,表示一个飞船进入数轴所在直线的初始坐标 $y_j$。 **保证给出的 $y_j$ 以不降序排序**。

输出格式


输出四行,每行一个整数,依次表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数,你的所有答案中的最大值、你的所有答案中的最小值。

输入输出样例

输入样例 #1

0
2 3
1 3
1
2
3

输出样例 #1

1
1
1
0

说明

### 样例 1 解释 数轴上 $1, 3$ 两点有虫洞。当飞船初始坐标为 $1$ 或 $3$ 时,可以直接进入虫洞,花费 $0s$;当初始坐标为 $2$ 时,有 $\frac 1 2$ 的概率向左一个单位,花费 $1s$ 进入虫洞,也有 $\frac 1 2$ 的概率向右一个单位,花费 $1s$ 进入虫洞,期望用时为 $\frac 1 2 \times (1 + 1) = 1$。 因此,三次询问的答案分别为 $0, 1, 0$。 ### 数据规模与约定 本题共有 $10$ 个测试点,每个测试点 $10$ 分。 - 对于 $10\%$ 的数据,保证 $n = 1$。 - 对于 $20\%$ 的数据,保证对于任意一个虫洞,总存在另一个虫洞,使得他们之间的距离不超过 $2$。例如,样例中两个虫洞的距离为 $2$。 - 对于 $30\%$ 的数据,保证对于任意一个虫洞,总存在另一个虫洞,使得他们之间的距离不超过 $3$。 - 对于 $50\%$ 的数据,保证 $x_i,q \leq 100$。 - 对于 $70\%$ 的数据,保证 $x_i, q \leq 10^5$。 - 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^5$,$1 \leq q \leq 5 \times 10^6$,$1 \leq x_i, y_j \leq 10^9$,$y_j$ 不小于 $x_i$ 中的最小值,且 $y_j$ 不大于 $x_i$ 中的最大值,$y_j$ 按照不降序给出。 ### 提示 - 如果你不知道什么是分数取模,可以参考如下的内容: 对于一个形如 $\frac a b$ 的既约分数,其中 $b \lt 998244353$,它对 $998244353$ 取模后的值为 $a \times b^{998244351} \bmod {998244353}$ 。 - 为了方便用脚造数据,数据**并不**保证 $x_i$ 互不相同。 - 请注意大量数据读入对程序效率造成的影响。 - 本题的特殊输出方式只是为了避免输出过大造成程序超时,与本题解法无关。 - 请注意,$T$ **不是**数据组数。 - 本题共有两个附加文件,见附加文件中的 zhuo.zip。