The XOR-OR Dilemma solution codechef

The XOR-OR Dilemma solution codechef

Chef has an array AA of length NN such that Ai=iAi=i.

In one operation, Chef can pick any two elements of the array, delete them from AA, and append either their bitwise XOR or their bitwise OR to AA.

Note that after each operation, the length of the array decreases by 11.

Let FF be the final number obtained after N1N−1 operations are made. You are given an integer XX, determine if you can get F=XF=X via some sequence of operations.

In case it is possible to get F=XF=X, print the operations too (see the section Output format for more details), otherwise print 1−1.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of a single line containing two space-separated integers NN and XX.

Output Format

For each test case, output 1−1 if it is impossible to get XX in the end. Otherwise print N1N−1 lines denoting the operations.

On each line, print

  • 1 x y1 x y if you want replace xx and yy with x OR yx OR y.
  • 2 x y2 x y if you want replace xx and yy with x XOR yx XOR y.

Note that xx and yy are the elements of the array at the time of applying the operation, and if either of them is not present in the array you will receive a WA verdict.


  • 1T50001≤T≤5000
  • 2N2152≤N≤215
  • 1X21611≤X≤216−1
  • The sum of NN over all test cases won’t exceed 21052⋅105.

Sample Input 1 

3 2
2 2
4 7

Sample Output 1 

2 1 3
1 2 2
1 1 2
1 3 3
1 3 4


Test case 11: The operations are as follows:

  • Initially, the array is A=[1,2,3]A=[1,2,3]
  • The first move removes 11 and 33 and appends their XORXOR, making the array A=[2,2]A=[2,2]
  • The second move removes 22 and 22 and appends their OROR, making the array A=[2]A=[2]

Test case 22: It can be shown that no sequence of operations can achieve F=2F=2 in this case.

Test case 33: The operations are as follows:

  • Initially, the array is A=[1,2,3,4]A=[1,2,3,4]
  • After the first move, the array is A=[3,4,3]A=[3,4,3]
  • After the second move, the array is A=[4,3]A=[4,3]
  • After the third move, the array is A=[7]

Leave a Comment

Your email address will not be published.