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: Runtime Error

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)]
pow_10_MOD = [pow(10, i, MOD) for i in range(50)]

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: Runtime Error

Solution code:
import numpy as np
n ,q = map(int, input().split())
a = np.ones(n, dtype = np.int)
for i in range(q):
  l, r, d = map(int, input().split())
  b = np.full(r-l+1, d)
  a[l-1:r] = b
  string = np.array_str(a).replace(" ", "").replace("[","").replace("]", "")
  print(int(string)%998244353)

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
# N: 処理する区間の長さ
INF = 2**31-1
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(2*N0)
mod = 998244353

modv = [0]*N0*2
modv[N0+N-2] = 1

for i in range(N-1):
    modv[N0+N-3-i] = (modv[N0+N-2-i]*10) % mod
# print(modv)
for i in range(N0-2, -1, -1):
    modv[i] = (modv[2*i+1] + modv[2*i+2]) % mod


def gindex(l, r):
    L = (l + N0) >> 1
    R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1
        R >>= 1

# 遅延伝搬処理


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = lazy[2*i] = v
        #data[2*i-1] = data[2*i] = v * modv[2*i-1] % mod
        data[2*i-1] = v*modv[2*i-1] % mod
        data[2*i] = v*modv[2*i] % mod
        # print(data)
        lazy[i-1] = None

# 区間[l, r)をxに更新


# print(modv)


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l
    R = N0 + r
    v = x
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = v
            data[R-1] = v * modv[R-1] % mod
        if L & 1:
            lazy[L-1] = v
            data[L-1] = v * modv[L-1] % mod
            L += 1
        L >>= 1
        R >>= 1
    for i in ids:
        data[i-1] = (data[2*i-1] + data[2*i]) % mod

# 区間[l, r)内の合計を求める


def query(l, r):
    propagates(*gindex(xl, r))
    # print(data)
    L = N0 + l
    R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R-1]
        if L & 1:
            s += data[L-1]
            L += 1
        L >>= 1
        R >>= 1
    return s


update(0, N, 1)

for i in range(Q):
    l, r, d = map(int, input().split())
    update(l-1, r, d)
    print(query(0, N) % mod)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin
    N,Q = map(int,input().split())
    squr = int(N**0.5)+1
    mod = 998244353
    """
    前処理
    """
    memo = [[0]*(N) for _ in range(10)]
    for i in range(10):
        for j in range(N):
            memo[i][j] = i*pow(10,N-j-1,mod)%mod

    memo2 = [[0]*(N) for _ in range(10)]
    for i in range(10):
        for j in range(N-2,-1,-1):
            memo2[i][j] += memo2[i][j+1]+memo[i][j]
            memo2[i][j] %= mod


    array = [memo[1][i] for i in range(N)]
    #bucket[i][0] => そのバケットの合計値
    #bucket[i][1] => そのバケットでの遅延評価値
    bucket = [[0,0] for _ in range(squr)]
    for i in range(N):
        belong = i//squr
        bucket[belong][0] += array[i]
        bucket[belong][1] %= mod

    for _ in range(Q):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        #lの所属している区間でbucketの遅延評価値のクリアを行う。
        LBelong = l//squr
        if bucket[LBelong][1] > 0:
            for i in range(LBelong*squr,(LBelong+1)*squr):
                array[i] = memo[bucket[LBelong][1]][i]
            bucket[LBelong][1] = 0

        #rの所属している区間でbucketの遅延評価値のクリアを行う。
        RBelong = r//squr
        if bucket[RBelong][1] > 0:
            for i in range(RBelong*squr,min((RBelong+1)*squr,N)):
                array[i] = memo[bucket[RBelong][1]][i]
            bucket[RBelong][1] = 0
        
        #クエリ区間の左端の余った部分を処理。
        while l//squr != l/squr and l <= r:
            #bucket更新
            bucket[l//squr][0] -= array[l]
            if bucket[l//squr][0] < 0:
                bucket[l//squr][0] += mod
            bucket[l//squr][0] += memo[d][l]
            bucket[l//squr][0] %= mod
            
            #array更新
            array[l] = memo[d][l]
            
            l += 1
        
        #クエリ区間の右端の余った部分を処理。
        while r != (r//squr+1)*squr-1 and l <= r:
            #bucket更新
            bucket[r//squr][0] -= array[r]
            if bucket[r//squr][0] < 0:
                bucket[r//squr][0] += mod
            bucket[r//squr][0] += memo[d][r]
            bucket[r//squr][0] %= mod
            
            #array更新
            array[r] = memo[d][r]
            
            r -= 1
        
        if l < r:
            bucketLeft = l//squr
            bucketRight = r//squr
            for belong in range(bucketLeft,bucketRight+1):
                belongLeft = belong*squr
                belongRight = belong*squr+squr-1
                if bucketRight != N-1:
                    tmp = memo2[d][belongLeft] - memo2[d][belongRight+1]
                else:
                    tmp = memo2[d][belongLeft]
                if tmp < 0:
                    tmp += mod
                bucket[belong][0] = tmp
                bucket[belong][1] = d
        ans = 0
        for i in range(squr):
            ans += bucket[i][0]
            ans %= mod
        print(ans)
main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        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 = self.e()
        smr = self.e()

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

        return self.op(sml, smr)

    def apply(self, l, r, f):
        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)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        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)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


M = 998244353

def e():
    # (v, b)
    return (0, 0)

def op(sl, sr):
    # print(sl, sr)
    return ((sl[0] + sr[0]) % M, (sl[1] + sr[1]) % M)

def mapping(fl, sr):
    if fl[0] == 0:
        return sr
    return ((sr[1]*fl[0]) % M, sr[1])

def composition(fl, fr):
    if fl[1] > fr[1]:
        return fl
    return fr

def im():
    return (0, -1)

@mt
def slv(N, Q, LRQ):
    A = []
    for i in range(N):
        v = pow(10, N-i-1, M)
        A.append((v << 32) + v)
    st = LazySegmentTree(op, e, mapping, composition, im, A)

    ans = []
    for i, (l, r, d) in enumerate(LRQ, start=1):
        l -= 1
        st.apply(l, r, (d, i))
        ans.append(st.prod(0, N)[0])
    return ans


def main():
    N, Q = read_int_n()
    LRQ = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, LRQ), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def yuni(n,e):
  s=n
  for i in range(e):
    s+=mod
    if s%e==0:
      return (s//e)%mod
N,Q=map(int,input().split())
mod=998244353
S="1"*N
L=[]#各桁までのmod
a=10
R=list()
for i in range(N):
  L.append(yuni(a-1,9))
  R.append(yuni(a,10))
  a*=10
  a%=mod
for i in range(Q):
  a,b,c=map(int,input().split())
  a,b=N-b+1,N-a+1
  s=L[a-2]
  if a==1:
    s=0
  t=L[b-1]
  k=L[-1]
  w=(yuni(R[b-a+1]-1,9))*R[a-1]*c
  qwe=(k-t+s+w)%mod
  print(qwe)
  qwe=qwe-k
  #ここからLの上書き
  L=L[:a-1]+[(s+(c*yuni(R[y+1]-1,9)*R[a-1]))%mod for y in range(b-a+1)]+[(qwe+L[b+y])%mod for y in range(N-b)]

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
numb = [0]*n
for num in range(q):
  l,r,d = map(int,input().split())
  for i in range(l-1,r):
    numb[i] = d
  print(atoi(numb)/998244353)

Submission status: Runtime Error

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder__bit_code = """
def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x


def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x
"""

atcoder._bit = types.ModuleType('atcoder._bit')
exec(_atcoder__bit_code, atcoder._bit.__dict__)


_atcoder_lazysegtree_code = """
import typing

# import atcoder._bit


class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = atcoder._bit._ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

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

    def get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

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

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        left += self._size
        right += self._size

        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push(right >> i)

        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None):
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return

            left += self._size
            right += self._size

            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)

            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2

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

    def max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])

    def _push(self, k: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id
"""

atcoder.lazysegtree = types.ModuleType('atcoder.lazysegtree')
atcoder.lazysegtree.__dict__['atcoder'] = atcoder
atcoder.lazysegtree.__dict__['atcoder._bit'] = atcoder._bit
exec(_atcoder_lazysegtree_code, atcoder.lazysegtree.__dict__)
LazySegTree = atcoder.lazysegtree.LazySegTree


_atcoder__math_code = """
import typing


def _is_prime(n: int) -> bool:
    '''
    Reference:
    M. Forisek and J. Jancina,
    Fast Primality Testing for Integers That Fit into a Machine Word
    '''

    if n <= 1:
        return False
    if n == 2 or n == 7 or n == 61:
        return True
    if n % 2 == 0:
        return False

    d = n - 1
    while d % 2 == 0:
        d //= 2

    for a in (2, 7, 61):
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = y * y % n
            t <<= 1
        if y != n - 1 and t % 2 == 0:
            return False
    return True


def _inv_gcd(a: int, b: int) -> typing.Tuple[int, int]:
    a %= b
    if a == 0:
        return (b, 0)

    # Contracts:
    # [1] s - m0 * a = 0 (mod b)
    # [2] t - m1 * a = 0 (mod b)
    # [3] s * |m1| + t * |m0| <= b
    s = b
    t = a
    m0 = 0
    m1 = 1

    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u  # |m1 * u| <= |m1| * s <= b

        # [3]:
        # (s - t * u) * |m1| + t * |m0 - m1 * u|
        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
        # = s * |m1| + t * |m0| <= b

        s, t = t, s
        m0, m1 = m1, m0

    # by [3]: |m0| <= b/g
    # by g != b: |m0| < b/g
    if m0 < 0:
        m0 += b // s

    return (s, m0)


def _primitive_root(m: int) -> int:
    if m == 2:
        return 1
    if m == 167772161:
        return 3
    if m == 469762049:
        return 3
    if m == 754974721:
        return 11
    if m == 998244353:
        return 3

    divs = [2] + [0] * 19
    cnt = 1
    x = (m - 1) // 2
    while x % 2 == 0:
        x //= 2

    i = 3
    while i * i <= x:
        if x % i == 0:
            divs[cnt] = i
            cnt += 1
            while x % i == 0:
                x //= i
        i += 2

    if x > 1:
        divs[cnt] = x
        cnt += 1

    g = 2
    while True:
        for i in range(cnt):
            if pow(g, (m - 1) // divs[i], m) == 1:
                break
        else:
            return g
        g += 1
"""

atcoder._math = types.ModuleType('atcoder._math')
exec(_atcoder__math_code, atcoder._math.__dict__)


_atcoder_modint_code = """
from __future__ import annotations
import typing

# import atcoder._math


class ModContext:
    context = []

    def __init__(self, mod: int) -> None:
        assert 1 <= mod

        self.mod = mod

    def __enter__(self) -> None:
        self.context.append(self.mod)

    def __exit__(self, exc_type: typing.Any, exc_value: typing.Any,
                 traceback: typing.Any) -> None:
        self.context.pop()

    @classmethod
    def get_mod(cls) -> int:
        return cls.context[-1]


class Modint:
    def __init__(self, v: int = 0) -> None:
        self._mod = ModContext.get_mod()
        if v == 0:
            self._v = 0
        else:
            self._v = v % self._mod

    def mod(self) -> int:
        return self._mod

    def val(self) -> int:
        return self._v

    def __iadd__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            self._v += rhs._v
        else:
            self._v += rhs
        if self._v >= self._mod:
            self._v -= self._mod
        return self

    def __isub__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            self._v -= rhs._v
        else:
            self._v -= rhs
        if self._v < 0:
            self._v += self._mod
        return self

    def __imul__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            self._v = self._v * rhs._v % self._mod
        else:
            self._v = self._v * rhs % self._mod
        return self

    def __ifloordiv__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            inv = rhs.inv()._v
        else:
            inv = atcoder._math._inv_gcd(rhs, self._mod)[1]
        self._v = self._v * inv % self._mod
        return self

    def __pos__(self) -> Modint:
        return self

    def __neg__(self) -> Modint:
        return Modint() - self

    def __pow__(self, n: int) -> Modint:
        assert 0 <= n

        return Modint(pow(self._v, n, self._mod))

    def inv(self) -> Modint:
        eg = atcoder._math._inv_gcd(self._v, self._mod)

        assert eg[0] == 1

        return Modint(eg[1])

    def __add__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            result = self._v + rhs._v
            if result >= self._mod:
                result -= self._mod
            return raw(result)
        else:
            return Modint(self._v + rhs)

    def __sub__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            result = self._v - rhs._v
            if result < 0:
                result += self._mod
            return raw(result)
        else:
            return Modint(self._v - rhs)

    def __mul__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            return Modint(self._v * rhs._v)
        else:
            return Modint(self._v * rhs)

    def __floordiv__(self, rhs: typing.Union[Modint, int]) -> Modint:
        if isinstance(rhs, Modint):
            inv = rhs.inv()._v
        else:
            inv = atcoder._math._inv_gcd(rhs, self._mod)[1]
        return Modint(self._v * inv)

    def __eq__(self, rhs: typing.Union[Modint, int]) -> bool:
        if isinstance(rhs, Modint):
            return self._v == rhs._v
        else:
            return self._v == rhs

    def __ne__(self, rhs: typing.Union[Modint, int]) -> bool:
        if isinstance(rhs, Modint):
            return self._v != rhs._v
        else:
            return self._v != rhs


def raw(v: int) -> Modint:
    x = Modint()
    x._v = v
    return x
"""

atcoder.modint = types.ModuleType('atcoder.modint')
atcoder.modint.__dict__['atcoder'] = atcoder
atcoder.modint.__dict__['atcoder._math'] = atcoder._math
exec(_atcoder_modint_code, atcoder.modint.__dict__)
ModContext = atcoder.modint.ModContext

Modint = atcoder.modint.Modint

import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy

# from atcoder.lazysegtree import LazySegTree
# from atcoder.modint import ModContext, Modint


def solve(grid, s):  # fix inputs here
    console("----- solving ------")
    console(grid, s)
    # grid = [(x-1, y-1, z) for x,y,z in grid]

    with ModContext(998244353):
        # n, q = map(int, sys.stdin.readline().split())

        cur = 1
        arr = []
        for i in range(s):
            arr.append(cur)
            cur = (cur*10) % 998244353
        arr = arr[::-1]
        console(arr)
        a = [(Modint(ai), 1) for ai in arr]

        def op(x: (Modint, int), y: (Modint, int)) -> (Modint, int):
            return x[0] + y[0], x[1] + y[1]

        e = Modint(0), 0

        def mapping(x: (Modint, Modint), y: (Modint, int)) -> (Modint, int):
            return x[0] * y[0] + x[1] * y[1], y[1]

        def composition(x: (Modint, Modint),
                        y: (Modint, Modint)) -> (Modint, Modint):
            return x[0] * y[0], x[0] * y[1] + x[1]

        id_ = Modint(1), Modint(0)

        lazy_segtree = LazySegTree(op, e, mapping, composition, id_, a)

        for l, r, b in grid:
            l -= 1
            console(l,r,b)
            c = 0
            lazy_segtree.apply(l, r, (Modint(b), Modint(c)))
            l = 0
            r = s
            print(lazy_segtree.prod(l, r)[0].val())

    # return a string (i.e. not a list or matrix)
    return ""  


def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    s, nrows = list(map(int,inp[0].split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for nrow in range(nrows):
        grid.append(list(map(int,inp[nrow + 1].split())))

    res = solve(grid, s)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    # print(res)

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
S="1"*N
for i in range(Q):
  L,R,D=map(int,input().split())
  for j in range(L,R+1)
    S[j]=D
  print(inr(S)%998244353)