Hooray! Berl II, the king of Berland is making a knight tournament. The king has already sent the message to all knights in the kingdom and they in turn agreed to participate in this grand event.

As for you, you're just a simple peasant. There's no surprise that you slept in this morning and were late for the tournament (it was a weekend, after all). Now you are really curious about the results of the tournament. This time the tournament in Berland went as follows:  There are n knights participating in the tournament. Each knight was assigned his unique number — an integer from 1 to n.  The tournament consisted of m fights, in the i-th fight the knights that were still in the game with numbers at least l_{i} and at most r_{i} have fought for the right to continue taking part in the tournament.  After the i-th fight among all participants of the fight only one knight won — the knight number x_{i}, he continued participating in the tournament. Other knights left the tournament.  The winner of the last (the m-th) fight (the knight number x_{m}) became the winner of the tournament. 

You fished out all the information about the fights from your friends. Now for each knight you want to know the name of the knight he was conquered by. We think that the knight number b was conquered by the knight number a, if there was a fight with both of these knights present and the winner was the knight number a.

Write the code that calculates for each knight, the name of the knight that beat him.


-----Input-----

The first line contains two integers n, m (2 ≤ n ≤ 3·10^5; 1 ≤ m ≤ 3·10^5) — the number of knights and the number of fights. Each of the following m lines contains three integers l_{i}, r_{i}, x_{i} (1 ≤ l_{i} < r_{i} ≤ n; l_{i} ≤ x_{i} ≤ r_{i}) — the description of the i-th fight.

It is guaranteed that the input is correct and matches the problem statement. It is guaranteed that at least two knights took part in each battle.


-----Output-----

Print n integers. If the i-th knight lost, then the i-th number should equal the number of the knight that beat the knight number i. If the i-th knight is the winner, then the i-th number must equal 0.


-----Examples-----
Input
4 3
1 2 1
1 3 3
1 4 4

Output
3 1 4 0 
Input
8 4
3 5 4
3 7 6
2 8 8
1 8 1

Output
0 8 4 6 4 8 6 1 


-----Note-----

Consider the first test case. Knights 1 and 2 fought the first fight and knight 1 won. Knights 1 and 3 fought the second fight and knight 3 won. The last fight was between knights 3 and 4, knight 4 won.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '#!/usr/bin/env python\n#pyrival orz\nimport os\nimport sys\nfrom io import BytesIO, IOBase\n\n"""\n    for _ in range(int(input())):\n    n,m=map(int,input().split())\n    n=int(input())\n    a = [int(x) for x in input().split()]\n"""\n\nclass SortedList:\n    def __init__(self, iterable=[], _load=200):\n        """Initialize sorted list instance."""\n        values = sorted(iterable)\n        self._len = _len = len(values)\n        self._load = _load\n        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n        self._list_lens = [len(_list) for _list in _lists]\n        self._mins = [_list[0] for _list in _lists]\n        self._fen_tree = []\n        self._rebuild = True\n\n    def _fen_build(self):\n        """Build a fenwick tree instance."""\n        self._fen_tree[:] = self._list_lens\n        _fen_tree = self._fen_tree\n        for i in range(len(_fen_tree)):\n            if i | i + 1 < len(_fen_tree):\n                _fen_tree[i | i + 1] += _fen_tree[i]\n        self._rebuild = False\n\n    def _fen_update(self, index, value):\n        """Update `fen_tree[index] += value`."""\n        if not self._rebuild:\n            _fen_tree = self._fen_tree\n            while index < len(_fen_tree):\n                _fen_tree[index] += value\n                index |= index + 1\n\n    def _fen_query(self, end):\n        """Return `sum(_fen_tree[:end])`."""\n        if self._rebuild:\n            self._fen_build()\n\n        _fen_tree = self._fen_tree\n        x = 0\n        while end:\n            x += _fen_tree[end - 1]\n            end &= end - 1\n        return x\n\n    def _fen_findkth(self, k):\n        """Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`)."""\n        _list_lens = self._list_lens\n        if k < _list_lens[0]:\n            return 0, k\n        if k >= self._len - _list_lens[-1]:\n            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\n        if self._rebuild:\n            self._fen_build()\n\n        _fen_tree = self._fen_tree\n        idx = -1\n        for d in reversed(range(len(_fen_tree).bit_length())):\n            right_idx = idx + (1 << d)\n            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n                idx = right_idx\n                k -= _fen_tree[idx]\n        return idx + 1, k\n\n    def _delete(self, pos, idx):\n        """Delete value at the given `(pos, idx)`."""\n        _lists = self._lists\n        _mins = self._mins\n        _list_lens = self._list_lens\n\n        self._len -= 1\n        self._fen_update(pos, -1)\n        del _lists[pos][idx]\n        _list_lens[pos] -= 1\n\n        if _list_lens[pos]:\n            _mins[pos] = _lists[pos][0]\n        else:\n            del _lists[pos]\n            del _list_lens[pos]\n            del _mins[pos]\n            self._rebuild = True\n\n    def _loc_left(self, value):\n        """Return an index pair that corresponds to the first position of `value` in the sorted list."""\n        if not self._len:\n            return 0, 0\n\n        _lists = self._lists\n        _mins = self._mins\n\n        lo, pos = -1, len(_lists) - 1\n        while lo + 1 < pos:\n            mi = (lo + pos) >> 1\n            if value <= _mins[mi]:\n                pos = mi\n            else:\n                lo = mi\n\n        if pos and value <= _lists[pos - 1][-1]:\n            pos -= 1\n\n        _list = _lists[pos]\n        lo, idx = -1, len(_list)\n        while lo + 1 < idx:\n            mi = (lo + idx) >> 1\n            if value <= _list[mi]:\n                idx = mi\n            else:\n                lo = mi\n\n        return pos, idx\n\n    def _loc_right(self, value):\n        """Return an index pair that corresponds to the last position of `value` in the sorted list."""\n        if not self._len:\n            return 0, 0\n\n        _lists = self._lists\n        _mins = self._mins\n\n        pos, hi = 0, len(_lists)\n        while pos + 1 < hi:\n            mi = (pos + hi) >> 1\n            if value < _mins[mi]:\n                hi = mi\n            else:\n                pos = mi\n\n        _list = _lists[pos]\n        lo, idx = -1, len(_list)\n        while lo + 1 < idx:\n            mi = (lo + idx) >> 1\n            if value < _list[mi]:\n                idx = mi\n            else:\n                lo = mi\n\n        return pos, idx\n\n    def add(self, value):\n        """Add `value` to sorted list."""\n        _load = self._load\n        _lists = self._lists\n        _mins = self._mins\n        _list_lens = self._list_lens\n\n        self._len += 1\n        if _lists:\n            pos, idx = self._loc_right(value)\n            self._fen_update(pos, 1)\n            _list = _lists[pos]\n            _list.insert(idx, value)\n            _list_lens[pos] += 1\n            _mins[pos] = _list[0]\n            if _load + _load < len(_list):\n                _lists.insert(pos + 1, _list[_load:])\n                _list_lens.insert(pos + 1, len(_list) - _load)\n                _mins.insert(pos + 1, _list[_load])\n                _list_lens[pos] = _load\n                del _list[_load:]\n                self._rebuild = True\n        else:\n            _lists.append([value])\n            _mins.append(value)\n            _list_lens.append(1)\n            self._rebuild = True\n\n    def discard(self, value):\n        """Remove `value` from sorted list if it is a member."""\n        _lists = self._lists\n        if _lists:\n            pos, idx = self._loc_right(value)\n            if idx and _lists[pos][idx - 1] == value:\n                self._delete(pos, idx - 1)\n\n    def remove(self, value):\n        """Remove `value` from sorted list; `value` must be a member."""\n        _len = self._len\n        self.discard(value)\n        if _len == self._len:\n            raise ValueError(\'{0!r} not in list\'.format(value))\n\n    def pop(self, index=-1):\n        """Remove and return value at `index` in sorted list."""\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        value = self._lists[pos][idx]\n        self._delete(pos, idx)\n        return value\n\n    def bisect_left(self, value):\n        """Return the first index to insert `value` in the sorted list."""\n        pos, idx = self._loc_left(value)\n        return self._fen_query(pos) + idx\n\n    def bisect_right(self, value):\n        """Return the last index to insert `value` in the sorted list."""\n        pos, idx = self._loc_right(value)\n        return self._fen_query(pos) + idx\n\n    def count(self, value):\n        """Return number of occurrences of `value` in the sorted list."""\n        return self.bisect_right(value) - self.bisect_left(value)\n\n    def __len__(self):\n        """Return the size of the sorted list."""\n        return self._len\n\n    def __getitem__(self, index):\n        """Lookup value at `index` in sorted list."""\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        return self._lists[pos][idx]\n\n    def __delitem__(self, index):\n        """Remove value at `index` from sorted list."""\n        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n        self._delete(pos, idx)\n\n    def __contains__(self, value):\n        """Return true if `value` is an element of the sorted list."""\n        _lists = self._lists\n        if _lists:\n            pos, idx = self._loc_left(value)\n            return idx < len(_lists[pos]) and _lists[pos][idx] == value\n        return False\n\n    def __iter__(self):\n        """Return an iterator over the sorted list."""\n        return (value for _list in self._lists for value in _list)\n\n    def __reversed__(self):\n        """Return a reverse iterator over the sorted list."""\n        return (value for _list in reversed(self._lists) for value in reversed(_list))\n\n    def __repr__(self):\n        """Return string representation of sorted list."""\n        return \'SortedList({0})\'.format(list(self))\n\ndef main():\n    n,m=map(int,input().split())\n    ans=[0]*n\n    st=SortedList([i for i in range(n)])\n    for _ in range(m):\n        l,r,x=map(int,input().split())\n        idx=st.bisect_left(l-1)\n        # print(l,r,x)\n        while idx<len(st):\n            cur=st[idx]\n            if cur>=r:\n                break\n            # print(cur)\n            ans[cur]=x\n            st.discard(cur)\n        ans[x-1]=0\n        st.add(x-1)\n    print(*ans)\n# region fastio\n\nBUFSIZE = 8192\n\n\nclass FastIO(IOBase):\n    newlines = 0\n\n    def __init__(self, file):\n        self._fd = file.fileno()\n        self.buffer = BytesIO()\n        self.writable = "x" in file.mode or "r" not in file.mode\n        self.write = self.buffer.write if self.writable else None\n\n    def read(self):\n        while True:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            if not b:\n                break\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines = 0\n        return self.buffer.read()\n\n    def readline(self):\n        while self.newlines == 0:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            self.newlines = b.count(b"\\n") + (not b)\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines -= 1\n        return self.buffer.readline()\n\n    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\n\n\nclass IOWrapper(IOBase):\n    def __init__(self, file):\n        self.buffer = FastIO(file)\n        self.flush = self.buffer.flush\n        self.writable = self.buffer.writable\n        self.write = lambda s: self.buffer.write(s.encode("ascii"))\n        self.read = lambda: self.buffer.read().decode("ascii")\n        self.readline = lambda: self.buffer.readline().decode("ascii")\n\n\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\ninput = lambda: sys.stdin.readline().rstrip("\\r\\n")\n\n# endregion\n\ndef __starting_point():\n    main()\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 30361