You are given an array $a$ of $n$ integers and a set $B$ of $m$ positive integers such that $1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$ for $1\le i\le m$, where $b_i$ is the $i$-th element of $B$.

You can make the following operation on $a$:

Select some $x$ such that $x$ appears in $B$.

Select an interval from array $a$ of size $x$ and multiply by $-1$ every element in the interval. Formally, select $l$ and $r$ such that $1\leq l\leq r \leq n$ and $r-l+1=x$, then assign $a_i:=-a_i$ for every $i$ such that $l\leq i\leq r$.

Consider the following example, let $a=[0,6,-2,1,-4,5]$ and $B={1,2\}$:

$[0,6,-2,-1,4,5]$ is obtained after choosing size $2$ and $l=4$, $r=5$.

$[0,6,2,-1,4,5]$ is obtained after choosing size $1$ and $l=3$, $r=3$.

Find the maximum $\sum\limits_{i=1}^n {a_i}$ you can get after applying such operation any number of times (possibly zero).


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2\leq n \leq 10^6$, $1 \leq m \leq \lfloor \frac{n}{2} \rfloor$) — the number of elements of $a$ and $B$ respectively.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\leq a_i \leq 10^9$).

The third line of each test case contains $m$ distinct positive integers $b_1,b_2,\ldots,b_m$ ($1 \leq b_i \leq \lfloor \frac{n}{2} \rfloor$) — the elements in the set $B$.

It's guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.


-----Output-----

For each test case print a single integer — the maximum possible sum of all $a_i$ after applying such operation any number of times.


-----Examples-----

Input
3
6 2
0 6 -2 1 -4 5
1 2
7 1
1 -1 1 -1 1 -1 1
2
5 1
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000
1
Output
18
5
5000000000


-----Note-----

In the first test, you can apply the operation $x=1$, $l=3$, $r=3$, and the operation $x=1$, $l=5$, $r=5$, then the array becomes $[0, 6, 2, 1, 4, 5]$.

In the second test, you can apply the operation $x=2$, $l=2$, $r=3$, and the array becomes $[1, 1, -1, -1, 1, -1, 1]$, then apply the operation $x=2$, $l=3$, $r=4$, and the array becomes $[1, 1, 1, 1, 1, -1, 1]$. There is no way to achieve a sum bigger than $5$.

Difficulty: VERY_HARD
Tags: Greedy algorithms

Number theory

Dynamic programming

Constructive algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]

def consec(a):
	tot = 0
	big = float('inf')
	neg = 0
	for guy in a:
		tot += abs(guy)
		if abs(guy) < big:
			big = abs(guy)
		if guy < 0:
			neg += 1
	if neg % 2 == 0:
		return (tot, tot - 2 * big)
	return (tot - 2 * big, tot)
import math

def main():
	(n, m) = I()
	a = I()
	b = I()
	g = b[0]
	for i in range(1, m):
		g = math.gcd(g, b[i])
	if g == 1:
		print(sum((abs(guy) for guy in a)))
		return
	tot = 0
	tot1 = 0
	for i in range(g):
		guy = []
		j = i
		while j < n:
			guy.append(a[j])
			j += g
		(x, y) = consec(guy)
		tot += x
		tot1 += y
	print(max(tot, tot1))
(t,) = I()
for _ in range(t):
	main()