Background

Original link: https://oier.team/problems/X4G.

Problem Description

A building with $n$ floors has $m$ elevators. Each elevator can be in two states: stationary or moving.

Initially, elevator $i$ is stationary on floor $i$. Given a permutation $p$ of $1 \sim m$, you want elevator $i$ to end up on floor $p_i$.

You can perform the following two types of operations:

• 0: Move time forward by one moment.
• x: where $x$ is a positive integer not exceeding $n$.
  • To perform this operation, the following must hold: there is no stationary elevator on floor $x$; the stationary elevator that is closest$^\dagger$ to floor $x$ exists and is unique.
  • Let $y$ be the index of the nearest stationary elevator, and $z$ be its position. Then elevator $y$ immediately becomes a moving elevator, and it will arrive at floor $x$ and become stationary before all operations after $\lvert x - z\rvert$ moments.

$^\dagger$: The distance between an elevator located on floor $a$ and floor $x$ is $\lvert a - x\rvert$.

Note: You must ensure that at any time, there are not two stationary elevators on the same floor.

For each testdata, there is a scoring parameter $o$. You must construct a plan whose total number of operations does not exceed $o$ in order to pass that testdata.

This problem uses a custom checker to verify whether your answer is correct. Therefore, if there are multiple valid plans, you only need to output any one.

Input Format

This problem input contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains four positive integers $Q, n, m, o$, representing the number of queries, the number of floors, the number of elevators, and the scoring parameter.
• The next $Q$ lines each contain $m$ integers $p_1, \ldots, p_m$, representing the target positions of the elevators.

Output Format

For each test case:

• Output a total of $2 Q$ lines. For each query, output two lines:
• The first line contains a non-negative integer $k$, the number of operations in your plan.
• The second line contains $k$ integers in $[0, n]$, representing your specific sequence of operations.

This problem uses a custom checker to verify whether your answer is correct. Therefore, if there are multiple valid plans, you only need to output any one.

2
2 4 2 12
1 2
2 1
1 10 5 30
5 4 3 2 1

0

9
3 4 0 0 1 0 2 0 0
16
6 6 6 6 6 0 1 0 2 0 3 0 4 0 5 0

1
1 6 5 30
5 4 3 2 1

16
6 6 6 6 6 0 1 0 2 0 3 0 4 0 5 0

Hint

[Sample Explanation #1]

This sample satisfies the constraints of Subtask 2.

For the first query of the first test case, no operation is needed.

For the second query of the first test case:

[Sample Explanation #2]

This sample satisfies the constraints of Subtask 7.

[Constraints]

This problem uses bundled test.

For all testdata, $1 \le T \le 20$, $2 \le m < n \le 5 \times 10^{4}$. It is guaranteed that $n, m, o$ simultaneously satisfy the constraints of some subtask above. $p$ is a permutation of $1 \sim m$. $1 \le Q \le 2\times 10^6$, $\sum o Q \le 2 \times 10^6$.

Translated by ChatGPT 5