Mio and Lucky Array
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3500
Tags: constructive algorithms, fft, math, strings

Mio has an array $$$a$$$ consisting of $$$n$$$ integers, and an array $$$b$$$ consisting of $$$m$$$ integers.

Mio can do the following operation to $$$a$$$:

- Choose an integer $$$i$$$ ($$$1 \leq i \leq n$$$) that has not been chosen before, then add $$$1$$$ to $$$a_i$$$, subtract $$$2$$$ from $$$a_{i+1}$$$, add $$$3$$$ to $$$a_{i+2}$$$ an so on. Formally, the operation is to add $$$(-1)^{j-i} \cdot (j-i+1) $$$ to $$$a_j$$$ for $$$i \leq j \leq n$$$.

Mio wants to transform $$$a$$$ so that it will contain $$$b$$$ as a subarray. Could you answer her question, and provide a sequence of operations to do so, if it is possible?

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$-10^5 \leq a_i \leq 10^5$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

The third line of the test case contains one integer $$$m$$$ ($$$2 \leq m \leq n$$$) — the number of elements in $$$b$$$.

The fourth line of the test case contains $$$m$$$ integers $$$b_1, b_2, \cdots, b_m$$$ ($$$-10^{12} \leq b_i \leq 10^{12}$$$), where $$$b_i$$$ is the $$$i$$$-th element of $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
If it is impossible to transform $$$a$$$ so that it contains $$$b$$$ as a subarray, output $$$-1$$$.

Otherwise, the first line of output should contain an integer $$$k$$$ ($$$0 \leq k \leq n$$$), the number of operations to be done.

The second line should contain $$$k$$$ distinct integers, representing the operations done in order.

If there are multiple solutions, you can output any.

Notice that you do not need to minimize the number of operations.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the sequence $$$a$$$ = $$$[1,2,3,4,5]$$$. One of the possible solutions is doing one operation at $$$i = 1$$$ (add $$$1$$$ to $$$a_1$$$, subtract $$$2$$$ from $$$a_2$$$, add $$$3$$$ to $$$a_3$$$, subtract $$$4$$$ from $$$a_4$$$, add $$$5$$$ to $$$a_5$$$). Then array $$$a$$$ is transformed to $$$a$$$ = $$$[2,0,6,0,10]$$$, which contains $$$b$$$ = $$$[2, 0, 6, 0, 10]$$$ as a subarray.

In the second test case, the sequence $$$a$$$ = $$$[1,2,3,4,5]$$$. One of the possible solutions is doing one operation at $$$i = 4$$$ (add $$$1$$$ to $$$a_4$$$, subtract $$$2$$$ from $$$a_5$$$). Then array $$$a$$$ is transformed to $$$a$$$ = $$$[1,2,3,5,3]$$$, which contains $$$b$$$ = $$$[3,5,3]$$$ as a subarray.

In the third test case, the sequence $$$a$$$ = $$$[-3, 2, -3, -4, 4, 0, 1, -2]$$$. One of the possible solutions is the following.

- Choose an integer $$$i=8$$$ to do the operation. Then array $$$a$$$ is transformed to $$$a$$$ = $$$[-3, 2, -3, -4, 4, 0, 1, -1]$$$.
- Choose an integer $$$i=6$$$ to do the operation. Then array $$$a$$$ is transformed to $$$a$$$ = $$$[-3, 2, -3, -4, 4, 1, -1, 2]$$$.
- Choose an integer $$$i=4$$$ to do the operation. Then array $$$a$$$ is transformed to $$$a$$$ = $$$[-3, 2, -3, -3, 2, 4, -5, 7]$$$.
- Choose an integer $$$i=3$$$ to do the operation. Then array $$$a$$$ is transformed to $$$a$$$ = $$$[-3, 2, -2, -5, 5, 0, 0, 1]$$$.
- Choose an integer $$$i=1$$$ to do the operation. Then array $$$a$$$ is transformed to $$$a$$$ = $$$[-2, 0, 1, -9, 10, -6, 7, -7]$$$.

The resulting $$$a$$$ is $$$[-2, 0, 1, -9, 10, -6, 7, -7]$$$, which contains $$$b$$$ = $$$[10, -6, 7, -7]$$$ as a subarray.

In the fourth test case, it is impossible to transform $$$a$$$ so that it contains $$$b$$$ as a subarray.

In the fifth test case, it is impossible to transform $$$a$$$ so that it contains $$$b$$$ as a subarray.

Example input:
5
5
1 2 3 4 5
5
2 0 6 0 10
5
1 2 3 4 5
3
3 5 3
8
-3 2 -3 -4 4 0 1 -2
4
10 -6 7 -7
5
1 2 3 4 5
4
1 10 1 1
5
0 0 0 0 0
2
10 12

Example output:
1
1 
1
4 
5
1 3 4 6 8 
-1
-1

Editorial:
Let's define $$$f_i = a_i + 2 a_{i-1} + a_{i-2}, g_i = b_i + 2b_{i-1} + b_{i-2}$$$. Cosidering after the operation on some index $$$i$$$, for any $$$j\ne i$$$, $$$f_j$$$ will remain the same; For $$$j=i$$$, $$$f_j$$$ will be increased by $$$1$$$. Then we can find the operation on $$$a$$$ is a single point operation on $$$f$$$.
It can be proved that the following conditions are equivalent to the condition that $$$b[1,m]$$$ can match $$$a[k+1,k+m]$$$:
$$$$$$ \left\{\begin{matrix} b_1=a_{k+1} \\ b_2 + b_1 = a_{k+2} + a_{k+1} \\ g_i = f_{k+i} (i \ge 3) \\ \end{matrix}\right. $$$$$$
For $$$i \le k+2$$$, operation on $$$i$$$ will make $$$a_{k+1}+a_{k+2} \gets a_{k+1} + a_{k+2} + (-1)^{k-i}$$$. So the second condition restricts the difference of operating times between odd positions and even positions among first $$$k+2$$$ positions. When conducting an operation on $$$i$$$ it will make $$$a_{k+1} \gets a_{k+1} + (k+2-i)\times (-1)^{k-i}$$$.
So we can convert the problem to: using $$$-0,+1,-2,+3,-4,+5\cdots,(-1)^n n$$$, to make the number of subtractions(operations which make $$$a_{k+1}$$$ be decreased) minus the number of additions(operations which make $$$a_{k+1}$$$ be increased) is $$$a$$$, and the final $$$a_{k+1}$$$ should be $$$b$$$.
Further, suppose I first select all the subtractions($$$-0,-2,-4,-6,\dots$$$), i.e. take all the operation on odd/even(depending on the parity of $$$k$$$) positions. If I don't want to select it afterwards, it can be regarded as a re-add operation, then the first and second restrictions can be converted to $$$a \gets a +\lfloor\frac{k+1}{2}\rfloor+1, b\gets b+\sum_{i= 0}^{\lfloor \frac{k+1}{2}\rfloor} 2i$$$, where $$$a$$$ indicates that $$$a$$$ numbers need to be selected, and $$$b$$$ indicates that the selected sum is $$$b$$$. All $$$b$$$ which satisfies $$$\sum_{i=0}^{a-1} i \le b \le \sum_{i=k+1-a}^{k+1} i$$$ are legal and easy to construct.
Next consider the third restriction, the constructor $$$f(k) = \sum_{i=3}^m (g_i-f_{i+k})(g_i-f_{i+k}-1)$$$. If $$$f_{i+k}=g_i$$$ or $$$f_{i+k}+1=g_i$$$, then the above formula is 0. Whether $$$f_{i+k}=g_i$$$ respectively represents whether we need to operate on $$$k+i$$$, otherwise the above formula must be greater than 0. If $$$b[1,m]$$$ matches $$$a[k+1,k+m]$$$, then $$$f(k) = 0$$$, otherwise it must not match. So consider how to calculate $$$f$$$. $$$$$$ f(k) = \sum_{i=3}^m f_{i+k}^2+g_i^2-2f_{i+k}g_i-g_i+f_i $$$$$$ For $$$2f_{i+k}g_i$$$ is in the form of differential convolution, $$$g$$$ can be flipped and converted into polynomial multiplication, which can be solved by FFT. The other items are also simple.
Considering that $$$f(k)$$$ may be quite large, you need to test several different prime numbers if you use NTT, in order to avoid hacking.
The total time complexity $$$O(n\log n)$$$.
Also the available $$$k$$$ which satisfies the third restriction can also be found using bitset, the total time complexity $$$O(\frac{n^2}{\omega})$$$.