Flipping Range Solution|Codeforces round #768 (div 2)

                                     Flipping Range

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

You can make the following operation on a$a$:

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

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

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

Find the maximum ∑i=1nai$\sum _{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$t$ (1≤t≤105$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$n$ and m$m$ (2≤n≤106$2\le n\le {10}^6$, 1≤m≤⌊n2⌋$1\le m\le \lfloor \frac{n}{2}\rfloor$) — the number of elements of a$a$ and B$B$ respectively.

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (−109≤ai≤109$-{10}^9\le a_i\le {10}^9$).

The third line of each test case contains m$m$ distinct positive integers b1,b2,…,bm$b_1,b_2,\dots ,b_m$ (1≤bi≤⌊n2⌋$1\le b_i\le \lfloor \frac{n}{2}\rfloor$) — the elements in the set B$B$.

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

Output

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

Note

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

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

Solution:

1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. #define OJ \
5. freopen("input.txt", "r", stdin); \
6. freopen("output.txt", "w", stdout);
7. ll bp(ll a,ll b,ll mod=LONG_LONG_MAX){
8. a%=mod;
9. ll res=1;
10. while(b>0){
11. if(b&1) res=res*a%mod;
12. a=a*a%mod;
13. b/=2;
14. }
15. return res;
16. }
17.  
18. int c(int x,int n){
19. return x^(n-1);
20. }
21.  
22. void solve(){
23. int n,k;
24. cin>>n>>k;
25. vector<int> a(n/2),b(n/2);
26. if(k==0){
27. for(int i=0;i<n/2;i++){
28. a[i]=i,b[i]=c(i,n);
29. }
30. }
31. else if(k>0 && k<n-1){
32. // k & n-1 0 & c(k)
33. for(int i=0;i<n/2;i++){
34. if(i==0) a[i]=0,b[i]=c(k,n);
35. else if(i==k || i==c(k,n)) a[i]=k,b[i]=n-1;
36. else a[i]=i,b[i]=c(i,n);
37. }
38. }
39. else if(n==4){
40. cout<<-1<<"\n";
41. return;
42. }
43. else {
44. a[0]=n-1,b[0]=n-2;
45. a[1]=n-3,b[1]=1;
46. a[2]=0,b[2]=2;
47. for(int i=3;i<n/2;i++){
48. a[i]=i,b[i]=c(i,n);
49. }
50. }
51. for(int i=0;i<n/2;i++) cout<<a[i]<<" "<<b[i]<<"\n";
52. }
53.  
54. int main(){
55. cin.tie(0);ios_base::sync_with_stdio(0);
56. int ttt=1;
57. cin>>ttt;
58. while(ttt--){
59. solve();
60. }
61. }
62.