P14024 [ICPC 2024 Nanjing R] Strips

There are $w$ cells arranged in a row, numbered from $1$ to $w$ from left to right. Among the cells, $n$ of them are red, $m$ of them are black, and the remaining $(w - n - m)$ cells are white. You need to cover all the red cells with some strips. Each strip must cover $k$ continuous cells. Find a way to cover all red cells while satisfying all the following constraints: - Each red cell is covered by a strip. - No black cell is covered by a strip. - No two strips cover the same cell. That is, each cell is covered by at most one strip. - The number of strips used is as small as possible.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains four integers $n$, $m$, $k$ and $w$ ($1 \le n, m \le 10^5$, $1 \le k \le w \le 10^9$, $n + m \le w$), indicating the number of red cells, the number of black cells, the length of each strip and the total number of cells. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le w$), indicating that cell $a_i$ is red. The third line contains $m$ integers $b_1, b_2, \cdots, b_m$ ($1 \le b_i \le w$), indicating that cell $b_i$ is black. It's guaranteed that the given $(n + m)$ cells are distinct. It's also guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $2 \times 10^5$.

For each test case: If it is possible to cover all the red cells while satisfying all constraints, first output one line containing one integer $c$ indicating the smallest number of strips used. Then output another line containing $c$ integers $l_1, l_2, \cdots, l_c$ ($1 \le l_i \le w - k + 1$) separated by a space, where $l_i$ is the left-most cell covered by the $i$-th strip. If there are multiple valid answers, you can output any of them. If it is not possible to do so, just output $\texttt{-1}$ in one line.