Retrieve back the Array codechef solution- Dazzler had an array of NN distinct non-negative integers. Somehow he lost the array, but he knows the bitwise XOR of all the elements in the array. You have to help him to retrieve the array. You are given two positive integers NN and XX. Construct an array AA of NN elements with the following conditions: For each ii (1≤i≤N1≤i≤N), 0≤Ai≤5⋅1050≤Ai≤5⋅105. All the elements in the array AA should be pairwise distinct, i.e, Ai≠AjAi≠Aj if i≠ji≠j The bitwise XOR of all the NN elements in the array should be equal to XX, i.e, A1⊕A2⊕…⊕AN=XA1⊕A2⊕…⊕AN=X, where ⊕⊕ denotes the bitwise XOR operation. If there are multiple possible solutions, you may print any of them.

Retrieve back the Array solution codechef

 

Dazzler had an array of NN distinct non-negative integers. Somehow he lost the array, but he knows the bitwise XOR of all the elements in the array. You have to help him to retrieve the array.

You are given two positive integers NN and XX. Construct an array AA of NN elements with the following conditions:

  • For each ii (1iN1≤i≤N), 0Ai51050≤Ai≤5⋅105.
  • All the elements in the array AA should be pairwise distinct, i.e, AiAjAi≠Aj if iji≠j
  • The bitwise XOR of all the NN elements in the array should be equal to XX, i.e, A1A2AN=XA1⊕A2⊕…⊕AN=X, where  denotes the bitwise XOR operation.

If there are multiple possible solutions, you may print any of them.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers NN and XX — the size of the array and the bitwise XOR of the entire array.

Output Format

For each test case, output the NN distinct non-negative integers satisfying the constraints above.

Constraints

  • 1T21051≤T≤2⋅105
  • 1N1051≤N≤105
  • 1X51051≤X≤5⋅105
  • 0Ai51050≤Ai≤5⋅105
  • The sum of NN over all test cases does not exceed 31053⋅105

Subtasks

  • Subtask 1 (30 points): 1X1051≤X≤105
  • Subtask 2 (70 points): 1X51051≤X≤5⋅105

Sample Input 1 

3
1 10
2 4
3 1

Sample Output 1 

10
7 3
5 6 2

Explanation

Test case 22: [7,3][7,3] is one possible array, because 73=47⊕3=4

Test case 33: [5,6,2][5,6,2] is one possible array, because 562=15⊕6⊕2=1. Another valid array is [8,20,29][8,20,29].

Leave a Comment

Your email address will not be published.