У 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\) удалением нескольких (возможно, нуля или всех) элементов с начала и нескольких (возможно, нуля или всех) элементов с конца.
Выходные данные
Если невозможно преобразовать \(a\) так, чтобы он содержал \(b\) в качестве подмассива, выведите \(-1\).
В противном случае первая строка вывода должна содержать целое число \(k\) (\(0 \leq k \leq n\)), количество операций, которые необходимо выполнить.
Вторая строка должна содержать \(k\) различных целых чисел, представляющих операции, выполняемые по порядку.
Если решений несколько, можно вывести любое.
Обратите внимание, что вам не нужно минимизировать количество операций.
Примечание
В первом наборе входных данных последовательность \(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\) в качестве подмассива.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|