You are given an array of n elements, initially all a[i] = 0. Q queries need to be performed. Each query contains three integers l, r, and x  and you need to change all a[i] to (a[i] | x) for all l ≤ i ≤ r.
Return the array after executing Q queries.
Example 1:
Input:
N=3, Q=2
U=[[1, 3, 1],
   [1, 3, 2]]
Output:
a[]={3,3,3}
Explanation: 
Initially, all elements of the array are 0. After execution of the
first query, all elements become 1 and after execution of the 
second query all elements become 3.
Example 2:
Input:
N=3, Q=2
U=[[1, 2, 1],
   [3, 3, 2]]
Output:
a[]={1,1,2}
Explanantion:
[0,0,0] => [1,1,0] => [1,1,2]
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function updateQuery() which takes the integer N,Q, and U a QX3 matrix containing the Q queries where U[i][0] is l_{i}, U[i][1] is r_{i} andU[i][2] is x_{i}.and it returns the final array a.
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
Constraints:
1<=N<=10^{5}
1<=Q<=10^{5}
1<=U[i][0] <= U[i][1]<=N
1<= U[i][2] <=10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution():

    def updateQuery(self, N, Q, U):

        #your code goes here

Solutions:
class Solution:

	def updateQuery(self, N, Q, U):
		dp = [[0] * 17 for _ in range(N + 1)]
		for (l, r, v) in U:
			l -= 1
			r -= 1
			for i in range(17):
				if 1 << i & v:
					dp[l][i] += 1
					dp[r + 1][i] -= 1
		for i in range(1, N):
			for j in range(17):
				dp[i][j] += dp[i - 1][j]
		ans = []
		for i in range(N):
			c = 0
			for j in range(17):
				if dp[i][j] > 0:
					c |= 1 << j
			ans.append(c)
		return ans


from collections import defaultdict

class Solution:

	def updateQuery(self, N, Q, U):
		ans = []
		add = defaultdict(list)
		remove = defaultdict(list)
		for x in U:
			add[x[0] - 1].append(x[2])
			remove[x[1]].append(x[2])
		arr = [0] * 32
		for i in range(N):
			if i in add:
				for j in add[i]:
					k = 0
					while j:
						if j & 1:
							arr[k] += 1
						j >>= 1
						k += 1
			if i in remove:
				for j in remove[i]:
					k = 0
					while j:
						if j & 1:
							arr[k] -= 1
						j >>= 1
						k += 1
			num = 0
			for i in range(32):
				if arr[i]:
					num += pow(2, i)
			ans.append(num)
		return ans


class Solution:

	def updateQuery(self, N, Q, U):
		count = [[0] * 17 for _ in range(N + 1)]
		for (left, right, x) in U:
			for b in range(17):
				if x & 1 << b:
					count[left - 1][b] += 1
					count[right][b] -= 1
		for i in range(1, N):
			for j in range(17):
				count[i][j] += count[i - 1][j]
		res = []
		for i in range(N):
			cur = 0
			for b in range(17):
				if count[i][b]:
					cur |= 1 << b
			res.append(cur)
		return res


class Solution:

	def updateQuery(self, N, Q, U):
		dp = [[0 for i in range(5)] for i in range(N + 1)]
		for i in U:
			(l, r, x) = i
			for j in range(5):
				val = int(x & 1 << j > 0)
				if val > 0:
					dp[l - 1][j] += 1
					dp[r][j] -= 1
		ans = []
		tmp = 0
		for j in range(5):
			if dp[0][j] > 0:
				tmp += 1 << j
			else:
				tmp += 0 << j
		ans.append(tmp)
		for i in range(1, n):
			tmp = 0
			for j in range(5):
				dp[i][j] += dp[i - 1][j]
				if dp[i][j] > 0:
					tmp += 1 << j
				else:
					tmp += 0 << j
			ans.append(tmp)
		return ans


class Solution:

	def updateQuery(self, N, Q, U):
		BCNT = 17
		upd = [[] for _ in range(N + 1)]
		(tmp, bits) = (0, [0] * BCNT)
		for (l, r, x) in U:
			upd[l - 1].append(x)
			upd[r].append(-x)
		ans = [0] * N
		for i in range(N):
			if upd[i]:
				for v in upd[i]:
					(v, sign) = (v, 1) if v > 0 else (-v, -1)
					for j in range(BCNT):
						if v & 1 << j:
							bits[j] += sign
				tmp = 0
				for j in range(BCNT):
					if bits[j]:
						tmp |= 1 << j
			ans[i] = tmp
		return ans


class Solution:

	def updateQuery(self, N, Q, U):
		arr = [[0 for j in range(32)] for i in range(N + 1)]
		maxbit = 0
		for (l, r, x) in U:
			bit = 0
			while x > 0:
				if x & 1 > 0:
					maxbit = max(maxbit, bit)
					arr[l][bit] += 1
					if r + 1 <= N:
						arr[r + 1][bit] -= 1
				bit += 1
				x >>= 1
		for i in range(1, N + 1):
			for j in range(maxbit + 1):
				arr[i][j] = arr[i][j] + arr[i - 1][j]
		res = []
		for i in range(1, N + 1):
			ans = 0
			for j in range(maxbit + 1):
				if arr[i][j] > 0:
					ans |= 1 << j
			res.append(ans)
		return res


from collections import defaultdict

class Solution:

	def updateQuery(self, N, Q, U):
		queries = defaultdict(list)
		mx = 0
		for (l, r, x) in U:
			queries[l - 1].append(+x)
			queries[r].append(-x)
			mx = max(mx, x)
		t = 1
		bits = []
		while t <= mx:
			bits.append(0)
			t *= 2
		nb = len(bits)
		ans = []
		acc = 0
		for i in range(N):
			for x in queries[i]:
				if x > 0:
					for j in range(nb):
						if x >> j & 1:
							bits[j] += 1
				else:
					x = -x
					for j in range(nb):
						if x >> j & 1:
							bits[j] -= 1
			if len(queries[i]) != 0:
				acc = sum((1 << i for (i, b) in enumerate(bits) if b > 0))
			ans.append(acc)
		return ans


class Solution:

	def updateQuery(self, N, Q, U):
		n = N
		q = Q
		u = U
		a = []
		for i in range(n + 1):
			a.append([0] * 17)
		for i in range(q):
			k = u[i]
			x = k[2]
			j = 0
			while x:
				r = x % 2
				a[k[0] - 1][j] += r
				a[k[1]][j] -= r
				j += 1
				x = x // 2
		for i in range(1, n + 1):
			for j in range(17):
				a[i][j] += a[i - 1][j]
		l = []
		for i in a:
			s = 1
		for i in range(n):
			x = 1
			p = 0
			for j in range(17):
				m = 1
				if a[i][j] == 0:
					m = 0
				p += x * m
				x *= 2
			l.append(p)
		return l


class Solution:

	def updateQuery(self, N, Q, U):
		arr = [[0 for i in range(5)] for i in range(N + 1)]
		for (i, j, k) in U:
			for l in range(5):
				if k & 1 << l != 0:
					arr[i - 1][l] += 1
					arr[j][l] -= 1
		for i in range(5):
			for j in range(1, N):
				arr[j][i] += arr[j - 1][i]
		ans = [0 for i in range(N + 1)]
		j = 0
		for num in arr:
			a = 0
			for i in range(5):
				if num[i] > 0:
					a += 1 << i
			ans[j] = a
			j += 1
		return ans[:-1]


import math

class Solution:

	def updateQuery(self, N, Q, U):
		ans = [0] * N
		add = dict()
		rem = dict()
		for x in U:
			if x[0] - 1 in add:
				add[x[0] - 1].append(x[2])
			elif x[0] - 1 not in add:
				add[x[0] - 1] = [x[2]]
			if x[1] in rem:
				rem[x[1]].append(x[2])
			elif x[1] not in rem:
				rem[x[1]] = [x[2]]
		arr = [0] * 32
		for i in range(N):
			if i in add and len(add[i]) > 0:
				for x in add[i]:
					j = 0
					while x:
						if x & 1:
							arr[j] += 1
						x >>= 1
						j += 1
			if i in rem and len(rem[i]) > 0:
				for x in rem[i]:
					j = 0
					while x:
						if x & 1:
							arr[j] -= 1
						x >>= 1
						j += 1
			num = 0
			for j in range(0, 32):
				if arr[j]:
					num += math.pow(2, j)
			ans[i] = int(num)
		return ans


class Solution:

	def updateQuery(self, N, Q, U):
		bits = 4
		dp = [[0 for j in range(bits)] for i in range(n + 1)]
		for i in U:
			(l, r, x) = i
			for j in range(bits):
				val = int(x & 1 << j > 0)
				dp[l - 1][j] += val
				dp[r][j] -= val
		tmp = 0
		arr = [0] * n
		for j in range(bits):
			if dp[0][j] > 0:
				val = 1
			else:
				val = 0
			tmp += val << j
		arr[0] = tmp
		for i in range(1, n):
			tmp = 0
			for j in range(bits):
				dp[i][j] += dp[i - 1][j]
				if dp[i][j] > 0:
					val = 1
				else:
					val = 0
				tmp += val << j
			arr[i] = tmp
		return arr


from sortedcontainers import SortedList

class Solution:

	def updateQuery(self, N, Q, U):
		N_BITS = 5
		das = [SortedList([[-1, -1], [N, N]]) for i in range(N_BITS)]
		for (l, r, v) in U:
			for i in range(N_BITS):
				if v & 1 << i == 0:
					continue
				ival = [l - 1, r - 1]
				ind = das[i].bisect_right(ival)
				(prev, nxt) = (das[i][ind - 1], das[i][ind])
				if prev[1] >= ival[1]:
					continue
				if ival[1] >= nxt[0]:
					ival[1] = max(ival[1], nxt[1])
					das[i].remove(nxt)
				if ival[0] <= prev[1]:
					ival[0] = min(ival[0], prev[0])
					das[i].remove(prev)
				das[i].add(ival)
		arr = [0] * N
		for i in range(N_BITS):
			for (l, r) in das[i][1:-1]:
				for j in range(l, r + 1):
					arr[j] |= 1 << i
		return arr


class Solution:

	def updateQuery(self, N, Q, U):
		N_BITS = 4
		das = [DifferenceArray(N) for i in range(N_BITS)]
		for (l, r, v) in U:
			for i in range(N_BITS):
				if v & 1 << i == 0:
					continue
				das[i].update(l - 1, r - 1, 1)
		arr = [0] * N
		for i in range(N_BITS):
			bit_arr = das[i].get()
			for j in range(N):
				if bit_arr[j] == 0:
					continue
				arr[j] |= 1 << i
		return arr

class DifferenceArray:

	def __init__(self, n) -> None:
		self.da = [0] * n

	def update(self, l, r, val):
		self.da[l] += val
		if r + 1 < len(self.da):
			self.da[r + 1] -= val

	def get(self):
		arr = [0] * len(self.da)
		arr[0] = self.da[0]
		for i in range(1, len(self.da)):
			arr[i] = arr[i - 1] + self.da[i]
		return arr


import math as mt

class Solution:
	size = mt.ceil(mt.log2(100000.0))

	def updateQuery(self, N, Q, U):
		size = 5
		temp = [[0] * size for _ in range(N + 1)]
		for i in range(Q):
			(l, r, x) = U[i]
			for b in range(size):
				f = 1 << b & x
				temp[l - 1][b] += int(f)
				temp[r][b] -= int(f)
		res = [0] * N
		prev = [0] * size
		for i in range(N + 1):
			for b in range(size):
				prev[b] += temp[i][b]
				if prev[b] > 0:
					res[i] |= 1 << b
		return res


import math as mt

class Solution:
	size = mt.ceil(mt.log2(100000.0))

	def updateQuery(self, N, Q, U):
		bits = 5
		dp = [[0 for j in range(bits)] for i in range(n + 1)]
		for i in U:
			(l, r, x) = i
			for j in range(bits):
				val = int(x & 1 << j > 0)
				dp[l - 1][j] += val
				dp[r][j] -= val
		tmp = 0
		arr = [0] * n
		for j in range(bits):
			if dp[0][j] > 0:
				val = 1
			else:
				val = 0
			tmp += val << j
		arr[0] = tmp
		for i in range(1, n):
			tmp = 0
			for j in range(bits):
				dp[i][j] += dp[i - 1][j]
				if dp[i][j] > 0:
					val = 1
				else:
					val = 0
				tmp += val << j
			arr[i] = tmp
		return arr


class Solution:

	def updateQuery(self, N, Q, U):
		d = [[0 for _ in range(N + 1)] for _ in range(30)]
		for (l, r, x) in U:
			l -= 1
			r -= 1
			k = 0
			while x > 0:
				if x & 1:
					d[k][l] += 1
					d[k][r + 1] -= 1
				k += 1
				x >>= 1
		pref = [0 for _ in range(30)]
		ans = []
		for i in range(n):
			cur = 0
			for j in range(30):
				pref[j] += d[j][i]
				if pref[j] > 0:
					cur += 2 ** j
			ans.append(cur)
		return ans


import math
from collections import deque

class Solution:

	def updateQuery(self, N, Q, U):
		MAX_N = 100000.0
		BITS = math.ceil(math.log2(MAX_N))
		a = [[0] * BITS for _ in range(N + 2)]
		for (l, r, x) in U:
			for i in range(BITS):
				mask = 1 << i
				if mask & x:
					a[l][i] += 1
					a[r + 1][i] -= 1
		results = [0] * N
		for i in range(1, N + 1):
			val = 0
			for j in range(BITS):
				a[i][j] += a[i - 1][j]
				if a[i][j] > 0:
					results[i - 1] |= 1 << j
		return results


class Solution:

	def updateQuery(self, N, Q, U):
		count = [[0] * 17 for _ in range(N + 1)]
		for (l, r, x) in U:
			(l, r) = (l - 1, r - 1)
			for b in range(17):
				if x & 1 << b:
					count[l][b] += 1
					count[r + 1][b] -= 1
		for i in range(1, N):
			for j in range(17):
				count[i][j] += count[i - 1][j]
		res = []
		for i in range(N):
			cur = 0
			for b in range(17):
				if count[i][b]:
					cur |= 1 << b
			res.append(cur)
		return res
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, q) = map(int, input().split())
		U = []
		for i in range(q):
			(l, r, x) = map(int, input().split())
			U.append([l, r, x])
		arr = Solution().updateQuery(n, q, U)
		for i in arr:
			print(i, end=' ')
		print()


class Solution:

	def updateQuery(self, N, Q, U):
		count = [[0] * 17 for _ in range(N + 1)]
		for (l, r, x) in U:
			(l, r) = (l - 1, r - 1)
			for b in range(17):
				if x & 1 << b:
					count[l][b] += 1
					count[r + 1][b] -= 1
		for i in range(1, N):
			for j in range(17):
				count[i][j] += count[i - 1][j]


class Solution:

	def updateQuery(self, N, Q, U):
		arr = [[0] * 17 for i in range(N + 1)]
		for (s, e, x) in U:
			(s, e) = (s - 1, e - 1)
			for b in range(17):
				if x & 1 << b:
					arr[s][b] += 1
					arr[e + 1][b] -= 1
		for i in range(1, N):
			for b in range(17):
				arr[i][b] += arr[i - 1][b]
		res = []
		for i in range(N):
			cur = 0
			for b in range(17):
				if arr[i][b]:
					cur = cur | 1 << b
			res.append(cur)
		return res


class Solution:

	def updateQuery(self, N, Q, U):
		arr = [[0] * 32 for _ in range(N)]
		ans = []
		for (l, r, x) in U:
			i = 31
			while x > 0:
				if x & 1:
					arr[l - 1][31 - i] += 1
					if r != N:
						arr[r][31 - i] -= 1
				x = x // 2
				i -= 1
		cur = [0] * 32
		for i in range(N):
			val = 0
			for j in range(31, -1, -1):
				cur[j] += arr[i][j]
				val = 2 * val + (1 if cur[j] else 0)
			ans.append(val)
		return ans


class Solution:

	def updateQuery(self, N, Q, U):
		bits = 5
		dp = [[0 for j in range(bits)] for i in range(n + 1)]
		for i in U:
			(l, r, x) = i
			for j in range(bits):
				val = int(x & 1 << j > 0)
				dp[l - 1][j] += val
				dp[r][j] -= val
		tmp = 0
		arr = [0] * n
		for j in range(bits):
			if dp[0][j] > 0:
				val = 1
			else:
				val = 0
			tmp += val << j
		arr[0] = tmp
		for i in range(1, n):
			tmp = 0
			for j in range(bits):
				dp[i][j] += dp[i - 1][j]
				if dp[i][j] > 0:
					val = 1
				else:
					val = 0
				tmp += val << j
			arr[i] = tmp
		return arr
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, q) = map(int, input().split())
		U = []
		for i in range(q):
			(l, r, x) = map(int, input().split())
			U.append([l, r, x])
		arr = Solution().updateQuery(n, q, U)
		for i in arr:
			print(i, end=' ')
		print()


import heapq

class Solution:

	def updateQuery(self, N, Q, U):
		LOG = 4
		U.sort(key=lambda x: x[1])
		U.sort(key=lambda x: x[0])
		solve = [1 for i in range(N + 1)]
		H = []
		s = 0
		mask = [0 for i in range(LOG)]
		pi = 0
		for xi in range(1, n + 1):
			while len(H) > 0 and H[0][0] < xi:
				(xj, xp) = heapq.heappop(H)
				for k in range(LOG):
					onK = int(U[xp][2] & 1 << k != 0)
					mask[k] -= onK
					if mask[k] == 0 and onK:
						s = s ^ 1 << k
			while pi < Q and U[pi][0] <= xi:
				heapq.heappush(H, (U[pi][1], pi))
				for k in range(LOG):
					onK = int(U[pi][2] & 1 << k != 0)
					mask[k] += onK
					if mask[k] == 1 and onK:
						s = s | 1 << k
				pi += 1
			solve[xi] = s
		return solve[1:]


class Solution:

	def updateQuery(self, N, Q, U):
		B = 17
		upd = [[] for i in range(N + 1)]
		(temp, bits) = (0, [0] * B)
		for (l, r, x) in U:
			upd[l - 1].append(x)
			upd[r].append(-x)
		ans = [0] * N
		for i in range(N):
			if upd[i]:
				for v in upd[i]:
					(v, sign) = (v, 1) if v > 0 else (-v, -1)
					for j in range(B):
						if v & 1 << j:
							bits[j] += sign
					temp = 0
					for j in range(B):
						if bits[j]:
							temp |= 1 << j
			ans[i] = temp
		return ans