Description

This is NS05. There is no sign of life left on the Leiben planet. Requesting rescue! Puer! Can you hear me? I will stay here and wait for your return.

Fusu is trapped on the Leiben planet. Zhuo Wenyu is piloting a spaceship and plans to travel through a wormhole to reach Leiben and rescue Fusu.

On a number line, there are $n$ wormholes. The coordinate of the $i$-th wormhole is $x_i$. Entering any one of these wormholes can directly take you to Leiben and rescue Fusu. After the spaceship reaches the straight line containing the number line, it will lose control due to the magnetic field. Each second, it will move one unit to the left or to the right with equal probability.

Zhuo Wenyu is very anxious. He gives $q$ initial coordinates where the spaceship enters the line of the number line. For each coordinate, he wants to know the expected number of seconds needed to reach a wormhole.

If the expected value you compute is a fraction, you need to output the value modulo $998244353$. For the definition of taking a fraction modulo a prime, you can refer to the content in “Hint”.

To avoid the output being too large, you only need to output four integers: the bitwise XOR of all answers (after taking modulo $998244353$, same below), how many of your answers are odd, the maximum among all your answers, and the minimum among all your answers.

Input Format

The first line contains an integer $T$, which is the index number corresponding to the test point.
The second line contains two integers, representing the number of wormholes $n$ and the number of initial coordinates $q$.
The third line contains $n$ integers. The $i$-th integer represents the coordinate of the $i$-th wormhole $x_i$.
The next $q$ lines each contain one integer, representing an initial coordinate $y_j$ where the spaceship enters the line of the number line.

It is guaranteed that $y_j$ are given in non-decreasing order.

Output Format

Output four lines, each containing one integer, in order: the bitwise XOR of all answers, how many answers are odd, the maximum answer, and the minimum answer.

0
2 3
1 3
1
2
3

1
1
1
0

Hint

Sample 1 Explanation

There are wormholes at points $1$ and $3$ on the number line. When the initial coordinate is $1$ or $3$, the spaceship can enter a wormhole immediately and costs $0s$. When the initial coordinate is $2$, there is a probability of $\frac 1 2$ to move one unit to the left, costing $1s$ to enter a wormhole, and also a probability of $\frac 1 2$ to move one unit to the right, costing $1s$ to enter a wormhole. The expected time is $\frac 1 2 \times (1 + 1) = 1$.

Therefore, the answers to the three queries are $0, 1, 0$.

Constraints and Conventions

This problem has $10$ test points, and each test point is worth $10$ points.

• For $10\%$ of the testdata, it is guaranteed that $n = 1$.
• For $20\%$ of the testdata, it is guaranteed that for any wormhole, there always exists another wormhole such that the distance between them is at most $2$. For example, in the sample, the distance between the two wormholes is $2$.
• For $30\%$ of the testdata, it is guaranteed that for any wormhole, there always exists another wormhole such that the distance between them is at most $3$.
• For $50\%$ of the testdata, it is guaranteed that $x_i, q \leq 100$.
• For $70\%$ of the testdata, it is guaranteed that $x_i, q \leq 10^5$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq q \leq 5 \times 10^6$, $1 \leq x_i, y_j \leq 10^9$. Also, $y_j$ is not less than the minimum of $x_i$, and $y_j$ is not greater than the maximum of $x_i$. The values $y_j$ are given in non-decreasing order.

Hint

• If you do not know what it means to take a fraction modulo a prime, you can refer to the following:

  For an irreducible fraction of the form $\frac a b$, where $b \lt 998244353$, its value modulo $998244353$ is $a \times b^{998244351} \bmod {998244353}$.

• To make it easier to generate data by hand, the data does not guarantee that all $x_i$ are distinct.

• Please note that reading a large amount of data may affect the efficiency of your program.

• This special output format is only to avoid TLE due to overly large output, and it is unrelated to the solution of this problem.

• Please note that $T$ is not the number of test cases.

• This problem has two additional files; see zhuo.zip in the attachment files.

Translated by ChatGPT 5