G. Mio и счастливый массив
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Mio есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел, и массив $$$b$$$, состоящий из $$$m$$$ целых чисел.

Mio может выполнить следующую операцию над $$$a$$$:

  • Выберите целое число $$$i$$$ ($$$1 \leq i \leq n$$$), которое не было выбрано ранее, затем прибавьте $$$1$$$ к $$$a_i$$$, вычтите $$$2$$$ из $$$a_{i+1}$$$ , добавьте $$$3$$$ к $$$a_{i+2}$$$ и так далее. Формально операция состоит в добавлении $$$(-1)^{j-i} \cdot (j-i+1) $$$ к $$$a_j$$$ для $$$i \leq j \leq n$$$.

Mio хочет преобразовать $$$a$$$ так, чтобы он содержал $$$b$$$ как подмассив. Не могли бы вы ответить на ее вопрос и указать последовательность операций для этого, если это возможно?

Массив $$$b$$$ является подмассивом массива $$$a$$$, если $$$b$$$ получается из $$$a$$$ удалением нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца.

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — количество элементов в $$$a$$$.

Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \cdots, a_n$$$ ($$$-10^5 \leq a_i \leq 10^5$$$), где $$$a_i$$$ — $$$i$$$-й элемент $$$a$$$.

Третья строка набора входных данных содержит одно целое число $$$m$$$ ($$$2 \leq m \leq n$$$) — количество элементов в $$$b$$$.

Четвертая строка набора входных данных содержит $$$m$$$ целых чисел $$$b_1, b_2, \cdots, b_m$$$ ($$$-10^{12} \leq b_i \leq 10^{12}$$$), где $$$b_i$$$ — $$$i$$$-й элемент $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Если невозможно преобразовать $$$a$$$ так, чтобы он содержал $$$b$$$ в качестве подмассива, выведите $$$-1$$$.

В противном случае первая строка вывода должна содержать целое число $$$k$$$ ($$$0 \leq k \leq n$$$), количество операций, которые необходимо выполнить.

Вторая строка должна содержать $$$k$$$ различных целых чисел, представляющих операции, выполняемые по порядку.

Если решений несколько, можно вывести любое.

Обратите внимание, что вам не нужно минимизировать количество операций.

Пример
Входные данные
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
Выходные данные
1
1 
1
4 
5
1 3 4 6 8 
-1
-1
Примечание

В первом наборе входных данных последовательность $$$a$$$ = $$$[1,2,3,4,5]$$$. Одним из возможных решений является выполнение одной операции при $$$i = 1$$$ (прибавьте $$$1$$$ к $$$a_1$$$, вычтите $$$2$$$ из $$$a_2$$$, прибавьте $$$3$$$ к $$$a_3$$$, вычтите $$$4$$$ из $$$a_4$$$, прибавьте $$$5$$$ до $$$a_5$$$). Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[2,0,6,0,10]$$$, который содержит $$$b$$$ = $$$[2, 0, 6, 0, 10]$$$ в качестве подмассива.

Во втором наборе входных данных последовательность $$$a$$$ = $$$[1,2,3,4,5]$$$. Одно из возможных решений — сделать одну операцию при $$$i = 4$$$ (прибавить $$$1$$$ к $$$a_4$$$, вычесть $$$2$$$ из $$$a_5$$$). Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[1,2,3,5,3]$$$, который содержит $$$b$$$ = $$$[3,5,3]$$$ в качестве подмассива.

В третьем наборе входных данных последовательность $$$a$$$ = $$$[-3, 2, -3, -4, 4, 0, 1, -2]$$$. Одним из возможных решений является следующее.

  • Выберите целое число $$$i=8$$$ для выполнения операции. Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[-3, 2, -3, -4, 4, 0, 1, -1]$$$.
  • Выберите целое число $$$i=6$$$, чтобы выполнить операцию. Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[-3, 2, -3, -4, 4, 1, -1, 2]$$$.
  • Выберите целое число $$$i=4$$$ для выполнения операции. Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[-3, 2, -3, -3, 2, 4, -5, 7]$$$.
  • Выберите целое число $$$i=3$$$ для выполнения операции. Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[-3, 2, -2, -5, 5, 0, 0, 1]$$$.
  • Выберите целое число $$$i=1$$$ для выполнения операции. Затем массив $$$a$$$ преобразуется в $$$a$$$ = $$$[-2, 0, 1, -9, 10, -6, 7, -7]$$$.

В результате $$$a$$$ равно $$$[-2, 0, 1, -9, 10, -6, 7, -7]$$$, что содержит $$$b$$$ = $$$[10, -6, 7, -7]$$$ в качестве подмассива.

В четвертом наборе входных данных невозможно преобразовать $$$a$$$ так, чтобы он содержал $$$b$$$ в качестве подмассива.

В пятом наборе входных данных невозможно преобразовать $$$a$$$ так, чтобы он содержал $$$b$$$ в качестве подмассива.