Given a list S that initially contains a single value 0. Below are the Q queries of the following types:
	0 X: Insert X in the list
	1 X: For every element A in S, replace it by A XOR X.
Print all the element in the list in increasing order after performing the given Q queries.
 
Example 1:
Input:
N = 5
Q[] = {{0, 6}, {0, 3}, {0, 2}, {1, 4}, {1, 5}}
Output:
1 2 3 7
Explanation:
[0] (initial value)
[0 6] (add 6 to list)
[0 6 3] (add 3 to list)
[0 6 3 2] (add 2 to list)
[4 2 7 6] (XOR each element by 4)
[1 7 2 3] (XOR each element by 5)
Thus sorted order after performing
queries is [1 2 3 7] 
Example 2:
Input:
N = 3
Q[] = {{0, 2}, {1, 3}, {0, 5}} 
Output :
1 3 5
Explanation:
[0] (initial value)
[0 2] (add 2 to list)
[3 1] (XOR each element by 3)
[3 1 5] (add 5 to list)
Thus sorted order after performing
queries is [1 3 5].
Your Task:  
You don't need to read input or print anything. Your task is to complete the function constructList() which takes an integer N the number of queries and Q a list of lists of length 2 denoting the queries as input and returns the final constructed list.
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(L), where L is only used for output specific requirements.
Constraints:
1 ≤ Length of Q ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3

class Solution:
    def constructList(self, Q, N):
        # code here 

Solutions:
class Solution:

	def constructList(self, Q, N):
		ans = []
		xor = 0
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 0:
				ans.append(Q[i][1] ^ xor)
			else:
				xor ^= Q[i][1]
		ans.append(xor)
		ans.sort()
		return ans


class Solution:

	def constructList(self, arr, n):
		ans = []
		xor = 0
		for i in range(n - 1, -1, -1):
			if arr[i][0] == 0:
				ans.append(arr[i][1] ^ xor)
			else:
				xor ^= arr[i][1]
		ans.append(xor)
		ans.sort()
		return ans


class Solution:

	def constructList(self, q, n):
		l = []
		xor = 0
		for i in range(len(q) - 1, -1, -1):
			if q[i][0] == 0:
				l.append(q[i][1] ^ xor)
			else:
				xor = xor ^ q[i][1]
		l.append(0 ^ xor)
		l.sort()
		return l


class Solution:

	def constructList(self, Q, N):
		res = [0]
		xors = []
		for (i, val) in Q:
			if i:
				xors.append((len(res), val))
			else:
				res.append(val)
		filt = 0
		j = len(res) - 1
		while 0 <= j:
			while len(xors) and j < xors[-1][0]:
				filt ^= xors[-1][1]
				xors.pop()
			res[j] ^= filt
			j -= 1
		res.sort()
		return res


class Solution:

	def constructList(self, Q, N):
		arr = []
		value = 0
		for (test, item) in reversed(Q):
			if test == 0:
				arr.append(item ^ value)
			else:
				value = item ^ value
		arr.append(value)
		return sorted(arr)


class Solution:

	def constructList(self, Q, N):
		output = []
		xor = 0
		for (v, x) in Q[::-1]:
			if v == 0:
				output.append(x ^ xor)
			else:
				xor ^= x
		output.append(0 ^ xor)
		output.sort()
		return output


class Solution:

	def constructList(self, Q, N):
		arr = [0]
		xor = []
		for i in range(N):
			if Q[i][0] == 0:
				arr.append(Q[i][1])
			else:
				xor.append([len(arr), Q[i][1]])
		if xor:
			for i in range(len(xor) - 1, 0, -1):
				cum_xor = xor[i][1]
				xor[i - 1][1] ^= cum_xor
			xor_idx = 0
			for i in range(len(arr)):
				arr[i] ^= xor[xor_idx][1]
				if i == xor[xor_idx][0] - 1:
					while xor_idx < len(xor) - 1 and xor[xor_idx][0] == xor[xor_idx + 1][0]:
						xor_idx += 1
					xor_idx += 1
					if xor_idx >= len(xor):
						break
		arr = sorted(arr)
		return arr


class Solution:

	def constructList(self, Q, N):
		lis = []
		x = 0
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 1:
				x ^= Q[i][1]
			elif Q[i][0] == 0:
				lis.append(x ^ Q[i][1])
		lis.append(0 ^ x)
		return sorted(lis)


class Solution:

	def constructList(self, Q, N):
		result = []
		xr = 0
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 0:
				result.append(Q[i][1] ^ xr)
			else:
				xr ^= Q[i][1]
		result.append(0 ^ xr)
		return sorted(result)


class Solution:

	def constructList(self, Q, N):
		res = []
		x = 0
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 0:
				res.append(Q[i][1] ^ x)
			else:
				x ^= Q[i][1]
		res.append(x)
		res.sort()
		return res


class Solution:

	def constructList(self, Q, N):
		re = []
		xr = 0
		for i in range(len(Q) - 1, -1, -1):
			if Q[i][0] == 0:
				re.append(Q[i][1] ^ xr)
			else:
				xr = xr ^ Q[i][1]
		re.append(xr)
		re.sort()
		return re


class Solution:

	def constructList(self, Q, N):
		ans = []
		xor = 0
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 0:
				ans.append(xor ^ Q[i][1])
			else:
				xor ^= Q[i][1]
		ans.append(xor)
		return sorted(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		Q = []
		for i in range(N):
			(type, val) = map(int, input().split())
			Q.append([type, val])
		ob = Solution()
		res = ob.constructList(Q, N)
		for i in res:
			print(i, end=' ')
		print()


class Solution:

	def constructList(self, Q, N):
		ans = []
		xor = 0
		i = len(Q) - 1
		while i >= 0:
			if Q[i][0] == 0:
				ans.append(Q[i][1] ^ xor)
			else:
				xor ^= Q[i][1]
			i -= 1
		ans.append(xor)
		ans.sort()
		return ans


class Solution:

	def constructList(self, Q, N):
		x = 0
		arr = []
		for q in Q[::-1]:
			if q[0] == 1:
				x = x ^ q[1]
			else:
				arr.append(x ^ q[1])
		arr.append(x)
		arr.sort()
		return arr


class Solution:

	def constructList(self, Q, N):
		l = [0]
		x = 0
		for (i, j) in Q:
			if i == 0:
				l.append(j ^ x)
			else:
				x = x ^ j
		for i in range(len(l)):
			l[i] = l[i] ^ x
		return sorted(l)


class Solution:

	def constructList(self, Q, N):
		t = 0
		l = []
		for val in Q:
			if val[0] == 1:
				t ^= val[1]
		ans = []
		ans.append(t)
		for val in Q:
			if val[0] == 0:
				l.append((val[1], t))
			else:
				t ^= val[1]
		for i in range(len(l)):
			ans.append(l[i][0] ^ l[i][1])
		return sorted(ans)


class Solution:

	def constructList(self, Q, N):
		xor = 0
		for i in range(N - 1, -1, -1):
			cur = Q[i]
			if cur[0] == 1:
				xor ^= cur[1]
			else:
				cur[1] ^= xor
		arr = [0 ^ xor]
		for ele in Q:
			if ele[0] == 0:
				arr.append(ele[1])
		return sorted(arr)


class Solution:

	def constructList(self, Q, N):
		res = []
		x = 0
		for (q, e) in Q[::-1]:
			if q:
				x = x ^ e
			else:
				res.append(e ^ x)
		res.append(0 ^ x)
		return sorted(res)


class Solution:

	def constructList(self, Q, N):
		Q = [(0, 0)] + Q
		xor = 0
		res = []
		for i in range(len(Q) - 1, -1, -1):
			if Q[i][0] == 0:
				res.append(Q[i][1] ^ xor)
			else:
				xor ^= Q[i][1]
		return sorted(res)


class Solution:

	def constructList(self, Q, N):
		S = []
		XOR = 0
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 1:
				XOR = XOR ^ Q[i][1]
			else:
				S.append(XOR ^ Q[i][1])
		S.append(XOR)
		return sorted(S)


class Solution:

	def constructList(self, Q, N):
		S = [0]
		xor_list = [0]
		for query in Q:
			op = query[0]
			val = query[1]
			if op == 0:
				S.append(val)
				xor_list.append(0)
			else:
				xor_list[-1] ^= val
		len_s = len(S)
		xor_val = 0
		for i in range(len_s - 1, -1, -1):
			if xor_list[i]:
				xor_val ^= xor_list[i]
			S[i] ^= xor_val
		S.sort()
		return S


class Solution:

	def constructList(self, Q, N):
		xor_sum = 0
		for q in Q:
			if q[0] == 1:
				xor_sum ^= q[1]
		ans = [xor_sum]
		for q in Q:
			if q[0] == 1:
				xor_sum ^= q[1]
			else:
				ans.append(q[1] ^ xor_sum)
		ans.sort()
		return ans


class Solution:

	def constructList(self, Q, N):
		xor = 0
		li = []
		for i in range(N - 1, -1, -1):
			if Q[i][0] == 0:
				li.append(Q[i][1] ^ xor)
			elif Q[i][0] == 1:
				xor ^= Q[i][1]
		li.append(xor)
		return sorted(li)


class Solution:

	def constructList(self, Q, N):
		self.l = []
		xor_aggregate = 0
		for i in range(len(Q) - 1, -1, -1):
			(operation, elem) = Q[i]
			if operation == 0:
				self.l.append(elem ^ xor_aggregate)
			elif operation == 1:
				xor_aggregate ^= elem
			else:
				continue
		self.l.append(xor_aggregate)
		self.l.sort()
		return self.l


class Solution:

	def constructList(self, Q, N):
		xor = 0
		result = []
		for i in range(N - 1, -1, -1):
			query = Q[i][0]
			val = Q[i][1]
			if query == 0:
				x = val ^ xor
				result.append(x)
			else:
				xor = xor ^ val
		result.append(xor)
		result.sort()
		return result


class Solution:

	def constructList(self, Q, N):
		l = [0]
		xor = 0
		for (task, num) in Q:
			if task == 1:
				xor = xor ^ num
			else:
				l.append(xor ^ num)
		for i in range(len(l)):
			l[i] ^= xor
		return sorted(l)


class Solution:

	def constructList(self, Q, N):
		xor = 0
		list = []
		for x in reversed(Q):
			if x[0] == 0:
				list.append(x[1] ^ xor)
			else:
				xor ^= x[1]
		list.append(xor)
		return sorted(list)


class Solution:

	def getXOR(self, x, y):
		return (x | y) & (~x | ~y)

	def constructList(self, Q, N):
		xor = 0
		ans = []
		for i in range(len(Q) - 1, -1, -1):
			if Q[i][0] == 0:
				ans.append(Q[i][1] ^ xor)
			else:
				xor ^= Q[i][1]
		ans.append(xor)
		ans.sort()
		return ans


class Solution:

	def constructList(self, Q, N):
		xoring = 0
		out = []
		Q.insert(0, [0, 0])
		for i in range(N + 1):
			if Q[i][0] == 1:
				xoring ^= Q[i][1]
		for i in range(N + 1):
			if Q[i][0] == 1:
				xoring ^= Q[i][1]
			else:
				out.append(Q[i][1] ^ xoring)
		out.sort()
		return out


class Solution:

	def constructList(self, q, n):
		xor = 0
		ans = []
		for i in range(n - 1, -1, -1):
			if q[i][0] == 0:
				ans.append(xor ^ q[i][1])
			elif q[i][0] == 1:
				xor = xor ^ q[i][1]
		ans.append(xor ^ 0)
		ans.sort()
		return ans


class Solution:

	def constructList(self, Q, N):
		ls = []
		xor = 0
		for (i, j) in reversed(Q):
			if i == 0:
				ls.append(j ^ xor)
			else:
				xor ^= j
		ls.append(xor)
		ls.sort()
		return ls


class Solution:

	def constructList(self, Q, N):
		xor_elem = 0
		res = []
		for (q, elem) in reversed(Q):
			if q == 1:
				xor_elem ^= elem
			else:
				res.append(elem ^ xor_elem)
		res.append(xor_elem)
		return sorted(res)


class Solution:

	def constructList(self, Q, N):
		arr = [0]
		op = [0, 0]
		l = 1
		for i in Q:
			if i[0] == 0:
				arr.append(i[1])
				op.append(0)
				l += 1
			else:
				op[0] ^= i[1]
				op[-1] ^= i[1]
		num = 0
		for i in range(l):
			num ^= op[i]
			arr[i] ^= num
		arr.sort()
		return arr


class Solution:

	def constructList(self, Q, N):
		cumulative_xor = 0
		result = []
		for i in range(N - 1, -1, -1):
			(cmd, x) = Q[i]
			if cmd == 0:
				result.append(int(x) ^ cumulative_xor)
			else:
				cumulative_xor ^= x
		result.append(cumulative_xor)
		return sorted(result)