#P7099. [yLOI2020] 灼

[yLOI2020] 灼

题目背景

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

——银临《灼》

题目描述

这里是 NS05,勒本星球已无生命反应,请求救援!普尔!——你听得到吗?我会一直在这里,等待你的归来。

扶苏被困在了勒本星球,灼闻羽驾驶着一架宇宙飞船正打算穿越虫洞到达勒本星球拯救扶苏。

在一条数轴上有 nn 个虫洞,第 ii 个虫洞的坐标为 xix_i。进入这些虫洞的任意一个都可以直接到达勒本星球拯救扶苏。飞船到达数轴所在直线上后,会因为磁场的效应失去操控能力,飞船每秒会等概率向左或向右移动一个单位长度。

灼闻羽非常焦急,他给出了 qq 个飞船进入数轴所在直线的初始坐标,对于每个坐标,他想知道期望需要多少秒才能到达一个虫洞。

如果你计算出的期望是个分数,你需要求出这个分数对 998244353998244353 取模的答案。有关分数取模的定义你可以参考「提示」中的内容。

为了避免输出过大,你只需要输出四个整数,分别表示你所有回答(对 998244353998244353 取模之后,下同)的按位异或之和、你共有多少次回答的答案是奇数,你的所有答案中的最大值、你的所有答案中的最小值。

输入格式

第一行是一个整数,表示测试点所对应的编号 TT
第二行有两个整数,分别表示虫洞的个数 nn 和初始坐标的个数 qq
第三行有 nn 个整数,第 ii 个整数表示第 ii 个虫洞的坐标 xix_i
接下来 qq 行,每行一个整数,表示一个飞船进入数轴所在直线的初始坐标 yjy_j

保证给出的 yjy_j 以不降序排序

输出格式

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

0
2 3
1 3
1
2
3
1
1
1
0

提示

样例 1 解释

数轴上 1,31, 3 两点有虫洞。当飞船初始坐标为 1133 时,可以直接进入虫洞,花费 0s0s;当初始坐标为 22 时,有 12\frac 1 2 的概率向左一个单位,花费 1s1s 进入虫洞,也有 12\frac 1 2 的概率向右一个单位,花费 1s1s 进入虫洞,期望用时为 12×(1+1)=1\frac 1 2 \times (1 + 1) = 1

因此,三次询问的答案分别为 0,1,00, 1, 0

数据规模与约定

本题共有 1010 个测试点,每个测试点 1010 分。

  • 对于 10%10\% 的数据,保证 n=1n = 1
  • 对于 20%20\% 的数据,保证对于任意一个虫洞,总存在另一个虫洞,使得他们之间的距离不超过 22。例如,样例中两个虫洞的距离为 22
  • 对于 30%30\% 的数据,保证对于任意一个虫洞,总存在另一个虫洞,使得他们之间的距离不超过 33
  • 对于 50%50\% 的数据,保证 xi,q100x_i,q \leq 100
  • 对于 70%70\% 的数据,保证 xi,q105x_i, q \leq 10^5
  • 对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^51q5×1061 \leq q \leq 5 \times 10^61xi,yj1091 \leq x_i, y_j \leq 10^9yjy_j 不小于 xix_i 中的最小值,且 yjy_j 不大于 xix_i 中的最大值,yjy_j 按照不降序给出。

提示

  • 如果你不知道什么是分数取模,可以参考如下的内容:

    对于一个形如 ab\frac a b 的既约分数,其中 b<998244353b \lt 998244353,它对 998244353998244353 取模后的值为 a×b998244351mod998244353a \times b^{998244351} \bmod {998244353}

  • 为了方便用脚造数据,数据并不保证 xix_i 互不相同。

  • 请注意大量数据读入对程序效率造成的影响。

  • 本题的特殊输出方式只是为了避免输出过大造成程序超时,与本题解法无关。

  • 请注意,TT 不是数据组数。

  • 本题共有两个附加文件,见附加文件中的 zhuo.zip。