356A - Knight Tournament - CodeForces Solution

import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b"\n") + (not b)
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode("ascii"))
		self.read = lambda: self.buffer.read().decode("ascii")
		self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



class SortedList:
	def __init__(self, iterable=[], _load=200):
		
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		
		if self._rebuild:
			self._fen_build()

		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return 0, k
		if k >= self._len - _list_lens[-1]:
			return len(_list_lens) - 1, k + _list_lens[-1] - self._len
		if self._rebuild:
			self._fen_build()

		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return idx + 1, k

	def _delete(self, pos, idx):
		
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens

		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1

		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		
		if not self._len:
			return 0, 0

		_lists = self._lists
		_mins = self._mins

		lo, pos = -1, len(_lists) - 1
		while lo + 1 < pos:
			mi = (lo + pos) >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi

		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1

		_list = _lists[pos]
		lo, idx = -1, len(_list)
		while lo + 1 < idx:
			mi = (lo + idx) >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi

		return pos, idx

	def _loc_right(self, value):
		
		if not self._len:
			return 0, 0

		_lists = self._lists
		_mins = self._mins

		pos, hi = 0, len(_lists)
		while pos + 1 < hi:
			mi = (pos + hi) >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi

		_list = _lists[pos]
		lo, idx = -1, len(_list)
		while lo + 1 < idx:
			mi = (lo + idx) >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi

		return pos, idx

	def add(self, value):
		
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens

		self._len += 1
		if _lists:
			pos, idx = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		
		_lists = self._lists
		if _lists:
			pos, idx = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		
		pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def __len__(self):
		
		return self._len

	def __getitem__(self, index):
		
		pos, idx = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

from bisect import bisect_left
n,m=map(int,input().strip().split())
ans=[0]*(n+1)
good=SortedList([i for i in range(1,n+1)])
for i in range(m):
	l,r,x=map(int,input().strip().split())
	ll=bisect_left(good,l)
	todel=[]
	for ind in range(ll,len(good)):
		i=good[ind]
		if i<=r:
			if i!=x:
				todel.append(i)
				ans[i]=x
		else:
			break
		for i in todel:
		good.remove(i)
print(*ans[1:])