Problem: You have a string S of length N. Initially, all characters in S are `1`s.

You will perform queries Q times. In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit). Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

* 1 \leq N, Q \leq 200,000
* 1 \leq L_i \leq R_i \leq N
* 1 \leq D_i \leq 9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q


Output

Print Q lines. In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Examples

Input

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1


Output

11222211
77772211
77333333
72333333
72311333


Input

200000 1
123 456 7


Output

641437905

Solution (in PYTHON3):

Solution:
import sys
input = sys.stdin.buffer.readline


class LazySegmentTree:
    def __init__(self, n, unitX, unitA, X_f, A_f, XA_map):
        self.n = n
        self.unitX = unitX
        self.unitA = unitA
        self.X_f = X_f  # (X, X) -> X
        self.A_f = A_f  # (A, A) -> A
        self.XA_map = XA_map  # (X, A) -> X
        self.X = [unitX] * (self.n + self.n)
        self.A = [unitA] * (self.n + self.n)

    def __getitem__(self, i):
        i += self.n
        self._propagate_above(i)
        return self.X[i]

    def __setitem__(self, i, x):
        i += self.n
        self._propagate_above(i)
        self.X[i] = x
        self._calc_above(i)

    def build(self, array):
        for i, val in enumerate(array, self.n):
            self.X[i] = val
        for i in range(self.n - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _calc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _propagate_above(self, i):
        k = i >> 1
        H = k.bit_length() - 1
        for h in range(H, -1, -1):
            i = k >> h
            if self.A[i] == self.unitA:
                continue
            self.X[i << 1] = self.XA_map(self.X[i << 1], self.A[i])
            self.X[i << 1 | 1] = self.XA_map(self.X[i << 1 | 1], self.A[i])
            self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i])
            self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
            self.A[i] = self.unitA

    def fold(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        xl = self.unitX
        xr = self.unitX
        while l < r:
            if l & 1:
                xl = self.X_f(xl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                xr = self.X_f(self.X[r], xr)
            l >>= 1
            r >>= 1
        return self.X_f(xl, xr)

    def apply(self, i, a):
        i += self.n
        self._propagate_above(i)
        self.X[i] = self.XA_map(self.X[i], a)
        self.A[i] = self.A_f(self.A[i], a)
        self._calc_above(i)

    def apply_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        while l < r:
            if l & 1:
                self.X[l] = self.XA_map(self.X[l], a)
                self.A[l] = self.A_f(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.X[r] = self.XA_map(self.X[r], a)
                self.A[r] = self.A_f(self.A[r], a)
            l >>= 1
            r >>= 1
        self._calc_above(l0)
        self._calc_above(r0)


n, q = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(q)]
MOD = 998244353


pow_ = [1] * (n + 1)
for i in range(n):
    pow_[i + 1] = (pow_[i] * 10) % MOD

digit = [[0] * (n + 1) for i in range(10)]
for i in range(n):
    for val in range(10):
        digit[val][i + 1] = (digit[val][i] + pow_[i] * val) % MOD

unitX = (0, 0)
def X_f(x1, x2):
   return ((x1[0] * pow_[x2[1]] + x2[0]) % MOD, x1[1] + x2[1])

unitA = -1
A_f = lambda a1, a2: a1 if a2 == unitA else a2
def XA_map(x, a):
    if a != unitA: x = (digit[a][x[1]], x[1])
    return x


lst = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map) 
lst.build([(1, 1) for i in range(n)])

ans = []
for l, r, d in queries:
    l -= 1
    lst.apply_range(l, r, d)
    ans.append(lst.fold(0, n)[0])
    
print(*ans, sep="\n")