← 返回题目列表

Codeforces · 1704/G

G. 澪和幸运阵列

中文机器翻译题面 查看原题

Mio 有一个由 $$$n$$$ 整数组成的数组 $$$a$$$ 和由 $$$m$$$ 整数组成的数组 $$$b$$$。

Mio可以对$$$a$$$执行以下操作:

- 选择一个之前没有选择过的整数 $$$i$$$ ($$$1 \leq i \leq n$$$),然后将 $$$1$$$ 添加到 $$$a_i$$$,从 $$$a_{i+1}$$$ 中减去 $$$2$$$,将 $$$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$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

测试用例的第三行包含一个整数 $$$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$$$ 是 $$$b$$$ 的第 $$$i$$$ 个元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

如果无法转换 $$$a$$$ 使其包含 $$$b$$$ 作为子数组,则输出 $$$-1$$$。

否则,输出的第一行应包含一个整数 $$$k$$$ ($$$0 \leq k \leq n$$$),即要完成的操作数。

第二行应包含 $$$k$$$ 不同的整数,表示按顺序完成的操作。

如果有多个解,则可以输出任何一个。

请注意,您不需要最小化操作数量。

示例

输入 #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 
1
4 
5
1 3 4 6 8 
-1
-1

注意

在第一个测试用例中,序列 $$$a$$$ = $$$[1,2,3,4,5]$$$。一种可能的解决方案是在 $$$i = 1$$$ 处进行一次操作(将 $$$1$$$ 添加到 $$$a_1$$$,从 $$$a_2$$$ 中减去 $$$2$$$,将 $$$3$$$ 添加到 $$$a_3$$$,从 $$$a_4$$$ 中减去 $$$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$$$,从 $$$a_5$$$ 中减去 $$$2$$$)。然后数组 $$$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$$$ 作为子数组。