#CF2066F. 诅咒
诅咒
F. 诅咒
每个测试点的时间限制: 秒
每个测试点的内存限制: 兆字节
给定两个整数数组: 和 。
你需要判断是否能够通过以下操作若干次(可能为零次)将数组 变换为数组 :
在 的所有非空子数组∗中,选择任意一个具有最大和的子数组,并将该子数组替换为任意一个非空整数数组。
如果可能,你需要构造出任意一个可行的操作序列。限制条件:在你的答案中,所有操作中用作替换的数组的长度之和不能超过 。每个数的绝对值不能超过 。
∗ 数组 是数组 的子数组,如果 可以通过从 的开头删除若干个(可能为零或全部)元素并从结尾删除若干个(可能为零或全部)元素得到。
输入
每个测试包含多个测试用例。第一行包含一个整数 ()——测试用例的数量。
每个测试用例的第一行包含两个整数 ()——数组 和 的长度。
每个测试用例的第二行包含 个整数 ()——数组 的元素。
每个测试用例的第三行包含 个整数 ()——数组 的元素。
保证所有测试用例的 之和不超过 。
保证所有测试用例的 之和不超过 。
输出
对于每个测试用例,如果无法将数组 变换为数组 ,输出 。
否则,在第一行输出操作次数 ()。然后按执行顺序输出操作,格式如下:
- 在每次操作的第一行,输出三个整数 ()。
- 在第二行,输出 个整数 ,表示将子数组 替换为数组 。
所有操作中 的总和必须不超过 。此外,必须满足 。
你不需要最小化操作次数。
示例
输入
3
4 3
2 -3 2 0
-3 -7 0
2 1
-2 -2
2
5 4
-5 9 -3 5 -9
-6 6 -1 -9
输出
4
3 4 1
-3
1 1 1
-3
2 2 1
-7
3 3 1
0
-1
3
2 4 1
-5
1 1 1
-6
2 2 2
6 -1
注意
在第一个测试用例中,初始数组的变换过程如下:
$[2, -3, 2, 0] \to [2, -3, -3] \to [-3, -3, -3] \to [-3, -7, -3] \to [-3, -7, 0]$
你可以选择输出空行或不输出。示例中的空行只是为了方便阅读。