Problem:


Score : 500 points

Problem Statement

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

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.

Sample Input 1

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

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.



Sample input:
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1


Sample output:
11222211
77772211
77333333
72333333
72311333

Submission status: Time Limit Exceeded

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np


def solve(N, Q, LRD):
    mod = 998244353
    p = 1
    n = 0
    p10 = np.empty(202020, dtype=np.int64)
    n11 = np.empty(202020, dtype=np.int64)
    for i in range(202020):
        p10[i] = p
        n11[i] = n
        p = p*10%mod
        n = (n*10+1)%mod

    identity = 0
    sqrtN = 512
    n_buckets = N//sqrtN+1
    Data_val = np.ones(n_buckets*sqrtN, dtype=np.int64)
    Data_val[N:] = 0
    Bucket_val = np.full(n_buckets, n11[sqrtN], dtype=np.int64)
    Lazy = np.full(n_buckets, identity, dtype=np.int64)
    M = N % sqrtN
    Bucket_val[n_buckets-1] = n11[M]

    def eval_data(k):
        if Lazy[k] != identity:
            l, r = k*sqrtN, (k+1)*sqrtN
            for i in range(l, r):
                Data_val[i] = Lazy[k]
            Lazy[k] = identity

    def apply(s, t, f):
        for k in range(s//sqrtN, (t-1)//sqrtN+1):
            l, r = k*sqrtN, (k+1)*sqrtN
            if s <= l and r <= t:
                Bucket_val[k] = f * n11[sqrtN] % mod
                Lazy[k] = f
            else:
                eval_data(k)
                for i in range(max(l, s), min(r, t)):
                    Data_val[i] = f
                Bucket_val[k] = 0
                for i in range(l, min(r, N)):
                    Bucket_val[k] = (Bucket_val[k] * 10 + Data_val[i]) % mod

    def get(i):
        k = i//sqrtN
        eval_data(k)
        return Data_val[i]

    def all_prod():
        res = 0
        for k in range(n_buckets-1):
            res = (res * p10[sqrtN] + Bucket_val[k]) % mod
        res = (res * p10[M] + Bucket_val[n_buckets-1]) % mod
        return res

    Ans = np.zeros(Q, dtype=np.int64)
    for i in range(Q):
        l, r, d = LRD[i]
        apply(l-1, r, d)
        ans = all_prod()
        Ans[i] = ans
        # print(Lazy)
        # print(Bucket_val)
        # print(Data_val)
        # print()

    return Ans


numba_compile([
    [solve, "i8[:](i8,i8,i8[:,:])"]
])


def main():
    N, Q = map(int, sys.stdin.buffer.readline().split())
    LRD = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(Q, 3)
    Ans = solve(N, Q, LRD)
    print("\n".join(map(str, Ans.tolist())))


main()

Submission status: Time Limit Exceeded

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np


def solve(N, Q, LRD):
    mod = 998244353
    p = 1
    n = 0
    p10 = np.empty(202020, dtype=np.int64)
    n11 = np.empty(202020, dtype=np.int64)
    for i in range(202020):
        p10[i] = p
        n11[i] = n
        p = p*10%mod
        n = (n*10+1)%mod

    identity = 0
    sqrtN = 3
    n_buckets = N//sqrtN+1
    Data_val = np.ones(n_buckets*sqrtN, dtype=np.int64)
    Data_val[N:] = 0
    Bucket_val = np.full(n_buckets, n11[sqrtN], dtype=np.int64)
    Lazy = np.full(n_buckets, identity, dtype=np.int64)
    M = N % sqrtN
    Bucket_val[n_buckets-1] = n11[M]

    def eval_data(k):
        if Lazy[k] != identity:
            l, r = k*sqrtN, (k+1)*sqrtN
            for i in range(l, r):
                Data_val[i] = Lazy[k]
            Lazy[k] = identity

    def apply(s, t, f):
        for k in range(s//sqrtN, (t-1)//sqrtN+1):
            l, r = k*sqrtN, (k+1)*sqrtN
            if s <= l and r <= t:
                Bucket_val[k] = f * n11[sqrtN] % mod
                Lazy[k] = f
            else:
                eval_data(k)
                for i in range(max(l, s), min(r, t)):
                    Data_val[i] = f
                Bucket_val[k] = 0
                for i in range(l, min(r, N)):
                    Bucket_val[k] = Bucket_val[k] * 10 + Data_val[i]

    def get(i):
        k = i//sqrtN
        eval_data(k)
        return Data_val[i]

    def all_prod():
        res = 0
        for k in range(n_buckets-1):
            res = (res * p10[sqrtN] + Bucket_val[k]) % mod
        res = (res * p10[M] + Bucket_val[n_buckets-1]) % mod
        return res

    Ans = np.zeros(Q, dtype=np.int64)
    for i in range(Q):
        l, r, d = LRD[i]
        apply(l-1, r, d)
        ans = all_prod()
        Ans[i] = ans
        # print(Lazy)
        # print(Bucket_val)
        # print(Data_val)
        # print()

    return Ans


numba_compile([
    [solve, "i8[:](i8,i8,i8[:,:])"]
])


def main():
    N, Q = map(int, sys.stdin.buffer.readline().split())
    LRD = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(Q, 3)
    Ans = solve(N, Q, LRD)
    print("\n".join(map(str, Ans.tolist())))


main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

Ref = [[0 for _ in range(100)] for _ in range(10)]
pow_2_lv = [pow(2,lv) for lv in range(30)]
P = 3*10**5+1
pow_10_MOD = [1 for i in range(P)]
for i in range(1,P):
  pow_10_MOD[i] = (pow_10_MOD[i-1] * 10) % MOD

for i in range(1,10):
  Ref[i][0] = i
  for s in range(1,30):
    Ref[i][s] += (Ref[i][s-1] * (pow(10, pow_2_lv[s-1], MOD) + 1)) % MOD
    Ref[i][s] %= MOD
#print(Ref)  
#####segfunc#####
def segfunc(x, y):
    return [(x[0] * pow_10_MOD[y[1]] + y[0]) % MOD, x[1] + y[1]]
#################

#####ide_ele#####
ide_ele = [0,0]
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v == ide_ele:
                continue
            lv = self.num.bit_length() - (2*i).bit_length() 
            upd = Ref[v[0]%10][lv]
            #print(v[0]%10, lv)
            self.lazy[2 * i] = [upd, pow_2_lv[lv]]
            self.lazy[2 * i + 1] = [upd, pow_2_lv[lv]]
            self.data[2 * i] = [upd, pow_2_lv[lv]]
            self.data[2 * i + 1] = [upd, pow_2_lv[lv]]
            self.lazy[i] = ide_ele

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        #print(l, r, " ids = ", ids)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                lv = self.num.bit_length() - l.bit_length() 
                #print(l, lv)
                upd = Ref[x[0]][lv]
                self.lazy[l] = [upd, pow_2_lv[lv]]
                self.data[l] = [upd, pow_2_lv[lv]]
                l += 1
            if r & 1:
                lv = self.num.bit_length() - (r-1).bit_length()
                upd = Ref[x[0]][lv]
                #print(r, lv)
                self.lazy[r - 1] = [upd, pow_2_lv[lv]]
                self.data[r - 1] = [upd, pow_2_lv[lv]]
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(self.data[l], res)
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
  
N, Q = map(int,input().split())
lst = LazySegmentTree([[1, 1] for _ in range(N)], segfunc, ide_ele)
#print(lst.data)
for _ in range(Q):
  L, R, D = map(int,input().split())
  L -= 1
  R -= 1
  lst.update(L, R+1, [D,1])
  print(lst.data[1][0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16579094


class LazySegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f  # (X, X) -> X
        self.g = g  # (X, A, size) -> X
        self.h = h  # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * \
                len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2 | 1])

        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2 | 1]

        self.A = [unitA] * (self.n * 2)

    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2 | 1])
            i >>= 1

    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])

    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2 | 1))
            i >>= 1

    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2 | 1] = self.h(self.A[i*2 | 1], self.A[i])
        self.A[i] = self.unitA

    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)

    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)

    def getrange(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)

        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)

    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)

    def operate_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.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1

        self.calc_above(l0)
        self.calc_above(r0)

    # Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False
    def max_right(self, l, z):
        if l >= self.n:
            return self.n
        l += self.n
        s = self.unitX
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.calc(l))):
                while l < self.n:
                    l *= 2
                    if z(self.f(s, self.calc(l))):
                        s = self.f(s, self.calc(l))
                        l += 1
                return l - self.n
            s = self.f(s, self.calc(l))
            l += 1
            if l & -l == l:
                break
        return self.n

    # Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False
    def min_left(self, r, z):
        if r <= 0:
            return 0
        r += self.n
        s = self.unitX
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.calc(r), s)):
                while r < self.n:
                    r = r * 2 + 1
                    if z(self.f(self.calc(r), s)):
                        s = self.f(self.calc(r), s)
                        r -= 1
                return r + 1 - self.n
            s = self.f(self.calc(r), s)
            if r & -r == r:
                break
        return 0


def main():
    P = 998244353
    poww = [0,1]
    powacc = [0,1]
    pows = 1
    for _ in range(200005):
        pows *= 10
        pows %= P
        poww.append(pows)
        tmp = powacc[-1]
        powacc.append((tmp+pows) % P)

    def f(x, y): return ((x[0]*poww[y[1]+1] + y[0]) % P, x[1]+y[1])
    def g(x, a, s): return ((a*powacc[x[1]]) % P, x[1]) if a !=10**10 else x
    def h(a, b): return b if b != 10**10 else a
    unitX = (0, 0)
    unitA = 10**10
    N, Q = map(int, input().split())
    A = [(1, 1)]*(N+2)
    st = LazySegmentTree(A, unitX, unitA, f, g, h)
    #print(st.getrange(0, N))

    for _ in range(Q):
        l, r, d = map(int, input().split())
        st.operate_range(l-1, r, d)
        print(st.getrange(0, N)[0])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from typing import Callable, List, TypeVar

S = TypeVar("S")  # 作用付きモノイドの型
F = TypeVar("F")  # 写像の型


class LazySegmentTree:
    """
    Lazy Segment Tree from https://atcoder.jp/contests/practice2/submissions/16775176
    References:
        https://tumoiyorozu.github.io/single-file-ac-library/document_ja/lazysegtree.html
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """

    __slots__ = ["e", "op", "id", "mapping", "composition", "_n", "_log", "_size", "tree", "lazy"]

    def __init__(self,
                 a: List[S],
                 e: S,
                 op: Callable[[S, S], S],
                 id_: F,
                 mapping: Callable[[F, S], S],
                 composition: Callable[[F, F], F]) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition

        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

        self.lazy = [id_] * self._size

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        return self.tree[k]

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        if l == r:
            return self.e

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push(r >> i)

        sml, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n

        if l == r:
            return

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)

        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp

        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)


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

mod = 998244353

base = [None] * N
base[N-1] = (1, 1)

for i in range(N-2, -1, -1):
    b = (base[i+1][1] * 10) % mod
    base[i] = (b, b)


def op(l, r):
    return [l[0]+r[0], l[1]+r[1]]


def mapping(l, r):
    if l == -1:
        return r
    return [(l*r[1]) % mod, r[1]]


def composition(l, r):
    if l == -1:
        return r
    return l


seg = LazySegmentTree(base, [0, 0], op, -1, mapping, composition)

for i in range(Q):
    L, R, D = map(int, input().split())
    seg.apply_range(L-1, R, D)
    print(seg.prod_all()[0] % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16579094


class LazySegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f  # (X, X) -> X
        self.g = g  # (X, A, size) -> X
        self.h = h  # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * \
                len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2 | 1])

        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2 | 1]

        self.A = [unitA] * (self.n * 2)

    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2 | 1])
            i >>= 1

    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])

    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2 | 1))
            i >>= 1

    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2 | 1] = self.h(self.A[i*2 | 1], self.A[i])
        self.A[i] = self.unitA

    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)

    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)

    def getrange(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)

        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)

    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)

    def operate_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.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1

        self.calc_above(l0)
        self.calc_above(r0)

    # Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False
    def max_right(self, l, z):
        if l >= self.n:
            return self.n
        l += self.n
        s = self.unitX
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.calc(l))):
                while l < self.n:
                    l *= 2
                    if z(self.f(s, self.calc(l))):
                        s = self.f(s, self.calc(l))
                        l += 1
                return l - self.n
            s = self.f(s, self.calc(l))
            l += 1
            if l & -l == l:
                break
        return self.n

    # Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False
    def min_left(self, r, z):
        if r <= 0:
            return 0
        r += self.n
        s = self.unitX
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.calc(r), s)):
                while r < self.n:
                    r = r * 2 + 1
                    if z(self.f(self.calc(r), s)):
                        s = self.f(self.calc(r), s)
                        r -= 1
                return r + 1 - self.n
            s = self.f(self.calc(r), s)
            if r & -r == r:
                break
        return 0


def main():
    P = 998244353
    poww = [0,1]
    powacc = [0,1]
    pows = 1
    for _ in range(200005):
        pows *= 10
        pows %= P
        poww.append(pows)
        tmp = powacc[-1]
        powacc.append((tmp+pows) % P)

    def f(x, y): return ((x[0]*pow(10,y[1],P) + y[0]) % P, x[1]+y[1])
    def g(x, a, s): return ((a*powacc[x[1]]) % P, x[1]) if a !=10**10 else x
    def h(a, b): return b if b != 10**10 else a
    unitX = (0, 0)
    unitA = 10**10
    N, Q = map(int, input().split())
    A = [(1, 1)]*(N+2)
    st = LazySegmentTree(A, unitX, unitA, f, g, h)
    #print(st.getrange(0, N))

    for _ in range(Q):
        l, r, d = map(int, input().split())
        st.operate_range(l-1, r, d)
        print(st.getrange(0, N)[0])


if __name__ == '__main__':
    main()