HDU 5683 zxa and xor

Problem Description

a1,a2,⋯,an of length 

n.

zxa thought only doing this was too boring, hence a function 

funct(x,y) defined by him, in which 

ax would be changed into 

y irrevocably and then compute 

⊗1≤i<j≤n(ai+aj) as return value.

zxa is interested to know, assuming that he called such function 

m times for this sequence, then what is the return value for each calling, can you help him?

tips:

⊗1≤i<j≤n(ai+aj) means that 

(a1+a2)⊗(a1+a3)⊗⋯⊗(a1+an)⊗(a2+a3)⊗(a2+a4)⊗⋯⊗(a2+an)⊗⋯⊗(an−1+an).

Input

T, represents there are 

T test cases.

For each test case:

The first line contains two positive integers 

n and 

m.

The second line contains 

n non-negative integers, represent 

a1,a2,⋯,an.

The next 

m lines, the 

i-th line contains two non-negative integers 

x and 

y, represent the 

i-th called function is 

funct(x,y).

There is a blank between each integer with no other extra space in one line.

1≤T≤1000,2≤n≤2⋅104,1≤m≤2⋅104,0≤ai,y≤109,1≤x≤n,1≤∑n,∑m≤105

Output

m lines, the 

i-th line a positive integer, repersents the return value for the 

i-th called function.

Sample Input

1

3 3

1 2 3

1 4

2 5

3 6

Sample Output

4

6

8

Hint

#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 2e4 + 10;
int T, x, y, a[maxn], ans, n, m;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);
    ans = 0;
    for (int i = 1; i <= n; i++)
    {
      scanf("%d", &a[i]);
      for (int j = i - 1; j; j--) ans ^= a[i] + a[j];
    }
    while (m--)
    {
      scanf("%d%d", &x, &y);
      (ans ^= a[x] + a[x]) ^= a[x] + y;
      for (int i = 1; i <= n; i++) (ans ^= a[i] + a[x]) ^= a[i] + y;
      a[x] = y;
      printf("%d\n", ans);
    }
  }
  return 0;
}