 0

# Favourite Operation

Difficulty: HARD Contributed By
Ashish Kumar
Avg. time to solve
30 min
Success Rate
70%

Problem Statement

#### You are given an array ‘A’ having ‘N’ integers and an integer ‘K’. You first calculate the bitwise ‘AND’ of all subarrays having size at most ‘K’. Then you take the bitwise ‘XOR’ of all these ‘AND’ results.

##### Example :
``````N = 3
K = 2
A = [ 1, 2, 3 ]

Explanation :

The bitwise ‘AND’ of all subarrays of size <= 2 are :

From index 1 :
Subarray of length 1 has ‘AND’ = 1.
Subarray of length 2 has ‘AND’ = 1 & 2 = 0.

From index 2 :
Subarray of length 1 has ‘AND’ = 2.
Subarray of length 2 has ‘AND’ = 2 & 3 = 2.

From index 3 :
Subarray of length 1 has ‘AND’ = 3.

‘XOR’ of all these ‘AND’ operations = 1 ^ 0 ^ 2 ^ 2 ^ 3 = 2.

So, final result = 2.
``````
##### Input Format :
``````The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers ‘N’ and ‘K’.

The second line of each test case contains an array ‘A’ of size ‘N’.
``````
##### Output format :
``````For each test case, print one integer denoting the final result after performing the operations.

Print the output of each test case in a new line.
``````
##### Note :
``````You don’t need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^5
1 <= K <= N
1 <= A[i] <= 10^5

Time Limit : 1 sec
``````
##### Sample Input 1 :
``````2
4 2
1 2 3 4
3 3
4 8 2
``````
##### Sample Output 1 :
``````6
14
``````
##### Explanation Of Sample Input 1 :
``````For test case 1 we have,

The bitwise ‘AND’ of all subarrays of size <= 2 is : 1, 2, 3, 4, 0, 2, 0.

The bitwise ‘XOR’ of all ‘AND’ operations is : 6

So, we output 6.

For test case 2 we have,

The bitwise ‘AND’ of all subarrays of size <= 3 is : 4, 8, 2, 0, 0, 0.

The bitwise ‘XOR’ of all ‘AND’ operations is : 14

So, we output 14.
``````
##### Sample Input 2 :
``````3
3 2
6 5 2
2 1
9 7
3 1
5 2 4
``````
##### Sample Output 2 :
``````5
14
3
``````   Console