学习了艺术平衡树后,利洲人遇到了以下问题。
给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您需要按顺序对 $$$a$$$ 执行精确的 $$$m$$$ 操作。每个操作由两个步骤组成。具体来说,在第 $$$i$$$ 操作中,您将获得一个整数 $$$x_i$$$,您将:
- 首先,选择中心索引 $$$u$$$ 和非负长度 $$$y$$$,使得区间 $$$[u-y, u+y]$$$ 完全位于 $$$[1, n]$$$ 内(即 $$$u - y \ge 1$$$ 和 $$$u + y \le n$$$)。对于每个 $$$1\le i\le y$$$,交换元素 $$$a_{u-i}$$$ 和 $$$a_{u+i}$$$。
- 然后, 标记 这 元素 位于索引 $$$x_i$$$。如果该元素已被标记,则不会发生任何事情。请注意,标记位于元素上,而不是索引上。这意味着如果将来的操作将某个元素与其他元素交换,该标记将保留在其上。
执行完所有 $$$m$$$ 操作后,您的任务是找到剩余所有元素的最小可能总和 未标记.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^5$$$) — $$$a$$$ 的长度和操作数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — $$$a$$$ 的元素。
第三行包含 $$$m$$$ 整数 $$$x_1, x_2, \ldots, x_m$$$ ($$$1 \le x_i \le n$$$) — 索引 已标记 在每个操作中。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 的最小可能总和 所有操作后的 未标记 元素。
示例
输入复制
67 41 2 3 4 5 6 71 2 3 47 41 -2 3 4 -5 -6 -77 6 5 47 521 -45 234 -8 423 12 -9876 6 6 6 67 5-21 45 -234 8 -423 -12 9877 7 7 7 77 3-1 2 -3 4 5 6 71 2 37 3-1 -2 -3 -4 -5 -6 -71 2 3
输出复制
6-20-362-6372-25
注意
在第一个测试用例中,一个最佳操作顺序如下:
- 选择中心 $$$u=4$$$ 和长度 $$$y=3$$$,$$$a$$$ 变为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_1=7$$$ 为 已标记.
- 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 仍为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_2=6$$$ 为 已标记.
- 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 仍为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_3=5$$$ 为 已标记.
- 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 仍为 $$$[7,6,5,4,3,2,1]$$$。那么,元素 $$$a_4=4$$$ 为 已标记.
未标记的元素是$$$1$$$、$$$2$$$和$$$3$$$,答案是$$$1+2+3=6$$$。
在第二个测试用例中,一个最佳操作顺序如下:
- 选择中心 $$$u=4$$$ 和长度 $$$y=3$$$,$$$a$$$ 变为 $$$[-7,-6,-5,4,3,-2,1]$$$。那么,元素 $$$a_7=1$$$ 为 已标记.
- 选择中心 $$$u=5$$$ 和长度 $$$y=1$$$,$$$a$$$ 变为 $$$[-7,-6,-5,-2,3,4,1]$$$。那么,元素 $$$a_6=4$$$ 为 已标记.
- 选择中心 $$$u=1$$$ 和长度 $$$y=0$$$,$$$a$$$ 保持 $$$[-7,-6,-5,-2,3,4,1]$$$。那么,元素 $$$a_5=3$$$ 为 已标记.
- 选择中心 $$$u=5$$$ 和长度 $$$y=1$$$,$$$a$$$ 变为 $$$[-7,-6,-5,4,3,-2,1]$$$。那么,元素 $$$a_4=4$$$ 为 已标记.
未标记的元素为 $$$-2$$$、$$$-5$$$、$$$-6$$$ 和 $$$-7$$$,答案为 $$$(-2)+(-5)+(-6)+(-7)=-20$$$。