Flipping Range
Contest: Codeforces Round 768 (Div. 1)
Difficulty rating: 2400
Tags: constructive algorithms, dp, greedy, number theory

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$$$:

1. Select some $$$x$$$ such that $$$x$$$ appears in $$$B$$$.
2. 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\}$$$:

1. $$$[0,6,-2,-1,4,5]$$$ is obtained after choosing size $$$2$$$ and $$$l=4$$$, $$$r=5$$$.
2. $$$[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 format:
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 format:
For each test case print a single integer — the maximum possible sum of all $$$a_i$$$ after applying such operation any number of times.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example 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

Example output:
18
5
5000000000

Editorial:
If we have $$$x, y \in B$$$ (assume $$$x > y$$$), since all elements of $$$B$$$ are at most $$$\lfloor\frac{n}{2}\rfloor$$$, it is possible to multiply all intervals of size $$$x-y$$$ by either multiplying an interval of size $$$x$$$ that starts at the position of the interval of size $$$x-y$$$, and an interval of size $$$y$$$ that ends at the same position as the interval $$$x$$$, or multiply an interval of size $$$x$$$ that ends at the same position as the interval of size $$$x-y$$$ and another interval of size $$$y$$$ that starts at the same position as the interval of size $$$x$$$.
For two elements $$$x, y \in B$$$ ($$$x > y$$$), it is possible to add $$$x-y$$$ to $$$B$$$, repeatedly doing this it is possible to get $$$\gcd(x, y)$$$.
Let $$$g = \gcd(b_1, b_2, ..., b_m : b_i \in B)$$$, by applying the previous reduction $$$g$$$ is the smallest element that can be obtained, and all other elements will be its multiples, then the problem is reduced to, multiplying intervals of size $$$g$$$ by $$$-1$$$ any number of times, maximize $$$\sum\limits_{i=1}^n{a_i}$$$.
Let's define the string $$$s = 000...00$$$ of size $$$n$$$ (0-indexed) such that $$$s_i = 0$$$ if the $$$i$$$-th element is not multiplied by $$$-1$$$ or $$$s_i = 1$$$ otherwise. The operation flips all values of $$$s$$$ in a substring of size $$$g$$$.
Let's define $$$f_x$$$ as the xor over all values $$$s_i$$$ such that $$$i\mod g = x$$$, note that $$$f_x$$$ is defined for the values $$$0 \le x \le g-1$$$.
In any operation, all values of $$$f$$$ change simultaneously, since they are all $$$0$$$ at the beginning only the states of $$$s$$$ such that all $$$f_i$$$ are equal are reachable.
To prove that all states of $$$s$$$ with all $$$f_i$$$ equal are reachable, let's start with any state of $$$s$$$ such that $$$f = 000...00$$$ and repeatedly select the rightmost $$$i$$$ such that $$$s_i=1$$$ and $$$i\geq g-1$$$ and flip the substring that ends in that position, after doing that as many times as possible, $$$s_i = 0$$$ for $$$g-1\leq i\leq n-1$$$. If $$$s_i=1$$$ for any $$$0\leq i < g$$$, then $$$f_i = 1$$$ which is a contradiction since $$$f_{g-1} = 0$$$ and all $$$f_i$$$ change simultaneously, then $$$s = 000...00$$$. The case with all values of $$$f$$$ equal to $$$1$$$ is similar.
After this, it is possible to solve the problem with $$$dp$$$.
Let $$$dp_{i,0}$$$ be the maximum sum of $$$a_i, a_{i-g}, a_{i-2\cdot{g}}, ..., a_{i-k\cdot{g}}$$$ such that $$$i-k\cdot{g}\equiv{i}(\mod{g})$$$ and $$$\bigoplus\limits_{k\geq 0, i-k\cdot g\geq 0} f_{i-k \cdot g}=0$$$ and $$$dp_{i,1}$$$ be the same such that $$$\bigoplus\limits_{k\geq 0, i-k\cdot g\geq 0} f_{i-k \cdot g}=1$$$.
The answer to the problem is $$$\max(\sum\limits_{i=n-g}^{n-1}{dp_{i,0}}, \sum\limits_{i=n-g}^{n-1}{dp_{i,1}} )$$$ (0-indexed).
This $$$dp$$$ can be computed in $$$O(n)$$$.