K. Strips
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.
Input

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$$$.

Output

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 -1 in one line.

Example
Input
4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2
Output
4
6 2 14 9
-1
2
1 4
-1