У Mio есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел, и массив $$$b$$$, состоящий из $$$m$$$ целых чисел.
Mio может выполнить следующую операцию над $$$a$$$:
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]$$$. Одним из возможных решений является следующее.
В результате $$$a$$$ равно $$$[-2, 0, 1, -9, 10, -6, 7, -7]$$$, что содержит $$$b$$$ = $$$[10, -6, 7, -7]$$$ в качестве подмассива.
В четвертом наборе входных данных невозможно преобразовать $$$a$$$ так, чтобы он содержал $$$b$$$ в качестве подмассива.
В пятом наборе входных данных невозможно преобразовать $$$a$$$ так, чтобы он содержал $$$b$$$ в качестве подмассива.
Название |
---|