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$$$ 作为子数组。