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:
class LazySegmentTree:
    """
    op: 区間取得クエリでreduceする際に使う演算子
    apply: 更新則の適用
    comp: 更新則の合成
    
    range_query: reduce(op, (apply(x,m) for x,m in zip(X,M)))
    
    満たすべき性質:
    
    集合X (要素)
    op[+]: X,X -> X
    (X, op)はモノイド
    
    集合M (更新則)
    comp[*]: M,M -> M
    (M, compose)はモノイド
    
    apply[f(x,m,n)]: X,M,Z+ -> X
    (Z+は区間長)
    
    f(x,e_M,n) = x
    f(x,m*n,p) = f(f(x,m,p),n,p)
    f(x,m,p)+f(y,m,q) = f(x+y,m,p+q)
    
    参考: https://algo-logic.info/segment-tree/#toc_id_3
    """
    @classmethod
    def all_identity(cls, op, op_e, comp, comp_e, apply, size):
        size = 1 << (size-1).bit_length()
        return cls(
            op,
            op_e,
            comp,
            comp_e,
            apply,
            [op_e]*(2*size),
            [comp_e]*size
        )

    @classmethod
    def from_initial_data(cls, op, op_e, comp, comp_e, apply, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [op_e]*(2*size)
        temp[size:size+len(data)] = data

        for i in reversed(range(size)):
            temp[i] = op(temp[2*i],temp[2*i+1])
        return cls(
            op,
            op_e,
            comp,
            comp_e,
            apply,
            temp,
            [comp_e]*size
        )

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, op, op_e, comp, comp_e, apply, data, lazy):
        self.op = op
        self.op_e = op_e
        self.comp = comp
        self.comp_e = comp_e
        self.apply = apply
        self.data = data
        self.lazy = lazy
        self.size = len(self.data)//2
        self.depth = self.size.bit_length()-1
        self._l_indices = [0]*self.depth
        self._r_indices = [0]*self.depth
    
    def _update_indices(self, i, l):
        m = i//(i&-i)
        i >>= 1
        for k in range(self.depth):
            l[k] = i if i < m else 0
            i >>= 1
    
    
    def _propagate_top_down(self):
        data = self.data
        lazy = self.lazy
        apply = self.apply
        comp = self.comp
        comp_e = self.comp_e
        k = self.size >> 1
        
        for i,j in zip(reversed(self._l_indices), reversed(self._r_indices)):
            if i > 0:
                temp = lazy[i]
                if temp != comp_e:
                    lazy[i] = comp_e
                    a = i << 1
                    b = a | 1
                    data[a] = apply(data[a], temp, k)
                    data[b] = apply(data[b], temp, k)
                    if k > 1:
                        lazy[a] = comp(lazy[a], temp)
                        lazy[b] = comp(lazy[b], temp)
            if i < j:
                temp = lazy[j]
                if temp != comp_e:
                    lazy[j] = comp_e
                    a = j << 1
                    b = a | 1
                    data[a] = apply(data[a], temp, k)
                    data[b] = apply(data[b], temp, k)
                    if k > 1:
                        lazy[a] = comp(lazy[a], temp)
                        lazy[b] = comp(lazy[b], temp)
            k >>= 1
            
    def _propagate_bottom_up(self):
        data = self.data
        op = self.op
        for i,j in zip(self._l_indices, self._r_indices):
            if i < j:
                data[j] = op(data[j<<1],data[j<<1|1])
            if i > 0:
                data[i] = op(data[i<<1],data[i<<1|1])
    
    def update_interval(self, l, r, m):
        lazy = self.lazy
        data = self.data
        comp = self.comp
        apply = self.apply
        
        l += self.size
        r += self.size
        self._update_indices(l, self._l_indices)
        self._update_indices(r, self._r_indices)
        self._propagate_top_down()
        k = 1
        while l < r:
            if l & 1:
                data[l] = apply(data[l],m,k)
                if k > 1:
                    lazy[l] = comp(lazy[l],m)
                l += 1
            if r & 1:
                r -= 1
                data[r] = apply(data[r],m,k)
                if k > 1:
                    lazy[r] = comp(lazy[r],m)
            l >>= 1
            r >>= 1
            k <<= 1
        self._propagate_bottom_up()
    
    def get_interval(self, l, r):
        data = self.data
        op = self.op
        
        l += self.size
        r += self.size
        self._update_indices(l, self._l_indices)
        self._update_indices(r, self._r_indices)
        self._propagate_top_down()
        
        lx = self.op_e
        rx = self.op_e
        while l < r:
            if l & 1:
                lx = op(lx, data[l])
                l += 1
            if r & 1:
                r -= 1
                rx = op(data[r], rx)
            l >>= 1
            r >>= 1
        return op(lx,rx)

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

MOD = 998244353

N,Q = map(int,readline().split())

ones = [0]*N
v = 0
for i in range(N):
    ones[i] = v
    v = (v*10+1)%MOD

power = [0]*N
v = 1
for i in range(N):
    power[i] = v
    v = (v*10)%MOD


# (sum, left_ind)
W = 20
MASK = (1 << W)-1

def compose(x,m):
    return x if m == 0 else m

def apply(x,m,l):
    return x if m == 0 else ((m*ones[l])%MOD << W)|(x&MASK)

def op(a,b):
    return ((((a>>W)+(b>>W)*power[(b&MASK-a&MASK)])%MOD) << W)|(a&MASK) 

seg = LazySegmentTree.from_initial_data(
            op,
            0, 
            compose,
            0,
            apply,
            [1<<W | i for i in range(N)])

m = map(int,read().split())

for l,r,d in zip(m,m,m):
    l,r = N-r,N-l
    seg.update_interval(l,r+1,d)
    print(seg.get_interval(0,N)>>20)