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()#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
ll getmax(vector<ll> nums) {
ll best_unflipped = nums[0];
ll best_flipped = -nums[0];
for (int i = 1; i < nums.size() - 1; i++) {
ll new_best_unflipped = -(1e18);
ll new_best_flipped = -(1e18);
// flip this one
new_best_flipped = max(best_flipped + nums[i], best_unflipped - nums[i]);
// not
new_best_unflipped = max(best_flipped - nums[i], best_unflipped + nums[i]);
best_flipped = new_best_flipped;
best_unflipped = new_best_unflipped;
}
best_flipped -= nums[nums.size() - 1];
best_unflipped += nums[nums.size() - 1];
// cout << best_flipped << " " << best_unflipped << endl;
return max(best_flipped, best_unflipped);
}
void solve() {
int n; cin >> n;
int m; cin >> m;
vector<ll> nums(n);
for (auto &a : nums) cin >> a;
vector<int> b(m);
for (auto &a : b) cin >> a;
int overall_gcd = b[0];
for (auto x : b) overall_gcd = __gcd(x, overall_gcd);
if (overall_gcd == 1) {
ll t = 0;
for (int i = 0; i < n; i++) t += abs(nums[i]);
cout << t << endl;
return;
}
// overall_gcd -= 1;
ll total_flip = 0;
ll total_unflip = 0;
for (int i = 0; i < overall_gcd; i++) {
vector<ll> newnums;
for (int j = i; j < n; j += overall_gcd) {
newnums.push_back(nums[j]);
}
total_unflip += getmax(newnums);
newnums[0] = -newnums[0];
// if (i == 0) newnums[1] = -newnums[1];
// for (auto a : newnums) cout << a << " ";
// cout << endl;
total_flip += getmax(newnums);
}
cout << max(total_flip, total_unflip) << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int tt = 1;
cin >> tt;
while (tt--) solve();
return 0;
}516. Longest Palindromic Subsequence | 468. Validate IP Address |
450. Delete Node in a BST | 445. Add Two Numbers II |
442. Find All Duplicates in an Array | 437. Path Sum III |
436. Find Right Interval | 435. Non-overlapping Intervals |
406. Queue Reconstruction by Height | 380. Insert Delete GetRandom O(1) |
332. Reconstruct Itinerary | 368. Largest Divisible Subset |
377. Combination Sum IV | 322. Coin Change |
307. Range Sum Query - Mutable | 287. Find the Duplicate Number |
279. Perfect Squares | 275. H-Index II |
274. H-Index | 260. Single Number III |
240. Search a 2D Matrix II | 238. Product of Array Except Self |
229. Majority Element II | 222. Count Complete Tree Nodes |
215. Kth Largest Element in an Array | 198. House Robber |
153. Find Minimum in Rotated Sorted Array | 150. Evaluate Reverse Polish Notation |
144. Binary Tree Preorder Traversal | 137. Single Number II |