write a go solution for F. XORificator 3000time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputAlice has been giving gifts to Bob for many years, and she knows that what he enjoys the most is performing bitwise XOR of interesting integers. Bob considers a positive integer x to be interesting if it satisfies xnotequivk(bmod2^i). Therefore, this year for his birthday, she gifted him a super-powerful "XORificator 3000", the latest model.Bob was very pleased with the gift, as it allowed him to instantly compute the XOR of all interesting integers in any range from l to r, inclusive. After all, what else does a person need for happiness? Unfortunately, the device was so powerful that at one point it performed XOR with itself and disappeared. Bob was very upset, and to cheer him up, Alice asked you to write your version of the "XORificator".InputThe first line of input contains a single integer t (1<=t<=10^4) — the number of XOR queries on the segment. The following t lines contain the queries, each consisting of the integers l, r, i, k (1<=l<=r<=10^18, 0<=i<=30, 0<=k<2^i).OutputFor each query, output a single integer — the XOR of all integers x in the range [l,r] such that xnotequivkmod2^i.ExampleInput61 3 1 02 28 3 715 43 1 057 2007 1 01010 1993 2 21 1000000000 30 1543Output2
2
13
0
4
1000000519
NoteIn the first query, the interesting integers in the range [1,3] are 1 and 3, so the answer will be 1oplus3=2.. Output only the code with no comments, explanation, or additional text.