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: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/lazysegtree>" namespace "atcoder" nogil:
    cdef cppclass lazy_segtree[S, OP, E, F, mapping, composition, id]:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)
        int max_right[G](int l)
        int min_left[G](int r)
cdef long mod = 998244353
cdef struct s_t:
    long v, s
ctypedef long f_t
cdef extern from *:
    ctypedef int op_t "myop"
    ctypedef int e_t "mye"
    ctypedef int m_t "mymapping"
    ctypedef int c_t "mycomposition"
    ctypedef int i_t "myid"
    ctypedef int g_t "myg"
    cdef s_t myop(s_t a, s_t b) nogil
    cdef s_t mye() nogil
    cdef s_t mymapping(f_t f, s_t x) nogil
    cdef f_t mycomposition(f_t f, f_t g) nogil
    cdef f_t myid() nogil
    cdef bool myg(s_t k) nogil
cdef s_t myop(s_t a, s_t b) nogil:
    cdef s_t c
    c.v = (a.v * b.s + b.v) % mod
    c.s = (a.s * b.s) % mod
    return c
cdef s_t mye() nogil:
    cdef s_t e
    e.v = 0
    e.s = 1
    return e
cdef f_t myid() nogil:
    return -1
cdef s_t mymapping(f_t f, s_t x) nogil:
    if f == myid(): return x
    cdef s_t y
    y.v = (x.s - 1) * 443664157 * f % mod
    y.s = x.s
    return y
cdef f_t mycomposition(f_t f, f_t g) nogil:
    if f == myid(): return g
    return f
from libc.stdio cimport getchar, printf
cdef inline int read() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef main():
    cdef int n = read(), i, l, r, d
    cdef s_t a
    a.v = 1
    a.s = 10
    cdef lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t] *seg = new lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t](vector[s_t](n, a))
    for i in range(read()):
        l, r, d = read(), read(), read()
        seg.apply(l - 1, r, d)
        printf('%ld\n', seg.all_prod().v)
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:

INF = 10**18
class LazySegTree:

    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n-1).bit_length()
        self.size = 1 << self.log
        self.data = [e]*(2*self.size)
        self.lazy = [id]*(self.size)

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

    def all_apply(self, k, f):
        self.data[k] = self.mapping(f, self.data[k])
        if k < self.size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def push(self, k):
        self.all_apply(2*k, self.lazy[k])
        self.all_apply(2*k+1, self.lazy[k])
        self.lazy[k] = self.id

    def build(self, lis):
        for i, l in enumerate(lis,self.size):
            self.data[i] = l
        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.data[p] = x
        for i in range(1,self.log+1):
            self.update(p>>i)

    def get(self, p):
        p += self.size
        for i in range(1, self.log+1):
            self.push(p >> i)
        return self.data[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 = smr = self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.data[1]

    def apply(self, p, f):
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.data[p] = self.mapping(f, self.data[p])
        for i in range(1, self.log+1):
            self.update(p >> i)

    def range_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 = l
        r2 = r
        while l2 < r2:
            if l2 & 1:
                self.all_apply(l2, f)
                l2 += 1
            if r2 & 1:
                r2 -= 1
                self.all_apply(r2, f)
            l2 >>= 1
            r2 >>= 1
        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 max_right(self, l, g):
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.data[l])):
                while l < self.size:
                    self.push(l)
                    l <<= 1
                    if g(self.op(sm, self.data[l])):
                        sm = self.op(sm, self.data[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.data[l])
            l += 1
            if (l & -l) == l:
                return self.n

    def min_left(self, r, g):
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push((r-1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.data[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2*r + 1
                    if g(self.op(self.data[r], sm)):
                        sm = self.op(self.data[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.data[r], sm)
            if (r & -r) == r:
                return 0

mod = 998244353
po32 = pow(2,32)
n,q = map(int,input().split())

def op(x, y):
    xv,xr = divmod(x,po32)
    yv,yr = divmod(y,po32)
    return ((xv+yv)%mod)*po32 + (xr+yr)%mod

def mapping(p, x):
    xv,xr = divmod(x, po32)
    if p == INF:
        return x
    return (p*xr % mod)*po32+xr

def composition(p, q):
    if p == INF:
        return q
    return p

lis = [0]*n
ten = 1
for i in range(n-1,-1,-1):
    lis[i] = ten%mod
    ten = (ten*10) % mod

l = [i*po32+i for i in lis]
e = 0
id = INF
lazyseg = LazySegTree(n, op, e, mapping, composition, id)
lazyseg.build(l)

for i in range(q):
    l,r,d = map(int,input().split())
    lazyseg.range_apply(l-1,r,d)
    print(lazyseg.all_prod()//po32)

Submission status: Accepted

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

INF = float("INF")
class LazySegTree:

    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n-1).bit_length()
        self.size = 1 << self.log
        self.data = [e]*(2*self.size)
        self.lazy = [id]*(self.size)

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

    def all_apply(self, k, f):
        self.data[k] = self.mapping(f, self.data[k])
        if k < self.size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def push(self, k):
        self.all_apply(2*k, self.lazy[k])
        self.all_apply(2*k+1, self.lazy[k])
        self.lazy[k] = self.id

    def build(self, lis):
        for i, l in enumerate(lis,self.size):
            self.data[i] = l
        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.data[p] = x
        for i in range(1,self.log+1):
            self.update(p>>i)

    def get(self, p):
        p += self.size
        for i in range(1, self.log+1):
            self.push(p >> i)
        return self.data[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 = smr = self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.data[1]

    def apply(self, p, f):
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.data[p] = self.mapping(f, self.data[p])
        for i in range(1, self.log+1):
            self.update(p >> i)

    def range_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 = l
        r2 = r
        while l2 < r2:
            if l2 & 1:
                self.all_apply(l2, f)
                l2 += 1
            if r2 & 1:
                r2 -= 1
                self.all_apply(r2, f)
            l2 >>= 1
            r2 >>= 1
        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 max_right(self, l, g):
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.data[l])):
                while l < self.size:
                    self.push(l)
                    l <<= 1
                    if g(self.op(sm, self.data[l])):
                        sm = self.op(sm, self.data[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.data[l])
            l += 1
            if (l & -l) == l:
                return self.n

    def min_left(self, r, g):
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push((r-1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.data[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2*r + 1
                    if g(self.op(self.data[r], sm)):
                        sm = self.op(self.data[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.data[r], sm)
            if (r & -r) == r:
                return 0

mod = 998244353
po32 = pow(2,32)
n,q = map(int,input().split())

def op(x, y):
    xv,xr = divmod(x,po32)
    yv,yr = divmod(y,po32)
    return ((xv+yv)%mod)*po32 + (xr+yr)%mod

def mapping(p, x):
    xv,xr = divmod(x, po32)
    if p == INF:
        return x
    return (p*xr % mod)*po32+xr

def composition(p, q):
    if p == INF:
        return q
    return p

lis = [0]*n
ten = 1
for i in range(n-1,-1,-1):
    lis[i] = ten%mod
    ten = (ten*10) % mod

l = [i*po32+i for i in lis]
e = 0
id = INF
lazyseg = LazySegTree(n, op, e, mapping, composition, id)
lazyseg.build(l)

for i in range(q):
    l,r,d = map(int,input().split())
    lazyseg.range_apply(l-1,r,d)
    print(lazyseg.all_prod()//po32)

Submission status: Accepted

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

INF = 10**18
class LazySegTree:

    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n-1).bit_length()
        self.size = 1 << self.log
        self.data = [e]*(2*self.size)
        self.lazy = [id]*(self.size)

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

    def all_apply(self, k, f):
        self.data[k] = self.mapping(f, self.data[k])
        if k < self.size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def push(self, k):
        self.all_apply(2*k, self.lazy[k])
        self.all_apply(2*k+1, self.lazy[k])
        self.lazy[k] = self.id

    def build(self, lis):
        for i, l in enumerate(lis,self.size):
            self.data[i] = l
        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.data[p] = x
        for i in range(1,self.log+1):
            self.update(p>>i)

    def get(self, p):
        p += self.size
        for i in range(1, self.log+1):
            self.push(p >> i)
        return self.data[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 = smr = self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.data[1]

    def apply(self, p, f):
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.data[p] = self.mapping(f, self.data[p])
        for i in range(1, self.log+1):
            self.update(p >> i)

    def range_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 = l
        r2 = r
        while l2 < r2:
            if l2 & 1:
                self.all_apply(l2, f)
                l2 += 1
            if r2 & 1:
                r2 -= 1
                self.all_apply(r2, f)
            l2 >>= 1
            r2 >>= 1
        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 max_right(self, l, g):
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.data[l])):
                while l < self.size:
                    self.push(l)
                    l <<= 1
                    if g(self.op(sm, self.data[l])):
                        sm = self.op(sm, self.data[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.data[l])
            l += 1
            if (l & -l) == l:
                return self.n

    def min_left(self, r, g):
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push((r-1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.data[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2*r + 1
                    if g(self.op(self.data[r], sm)):
                        sm = self.op(self.data[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.data[r], sm)
            if (r & -r) == r:
                return 0

mod = 998244353
po32 = pow(2,32)
n,q = map(int,input().split())

def op(x, y):
    xv,xr = divmod(x,po32)
    yv,yr = divmod(y,po32)
    return ((xv+yv)%mod)*po32 + (xr+yr)%mod

def mapping(p, x):
    xv,xr = divmod(x, po32)
    if p == INF:
        return x
    return (p*xr % mod)*po32+xr

def composition(p, q):
    if p == INF:
        return q
    return p

lis = [0]*n
ten = 1
for i in range(n-1,-1,-1):
    lis[i] = ten%mod
    ten = (ten*10) % mod

l = [i*po32+i for i in lis]
e = 0
id = INF
lazyseg = LazySegTree(n, op, e, mapping, composition, id)
lazyseg.build(l)

for i in range(q):
    l,r,d = map(int,input().split())
    lazyseg.range_apply(l-1,r,d)
    print(lazyseg.all_prod()//po32)

Submission status: Accepted

Solution code:
import sys
import numpy as np

def solve(inp):
    def bit_length(x):
        ret = 0
        while x:
            x >>= 1
            ret += 1
        return ret
    MOD = 998244353
    e = 0
    id_x = -1

    n = inp[0]
    log = bit_length(n)
    size = 1 << log
    d = [e] * (2 * size)
    lz = [id_x] * size

    def op(a, b):
        a1, a2 = a >> 32, a % (1 << 32)
        b1, b2 = b >> 32, b % (1 << 32)
        c1 = (a1 + b1) % MOD
        c2 = (a2 + b2) % MOD
        return (c1 << 32) + c2

    def mapping(x, a):
        if x == -1:
            return a
        a1, a2 = a >> 32, a % (1 << 32)
        c1 = (x * a2) % MOD
        c2 = a2
        return (c1 << 32) + c2

    def composition(x, y):
        if x == -1:
            return y
        return x

    def update(k):
        d[k] = op(d[2 * k], d[2 * k + 1])

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

    def push(k):
        all_apply(2 * k, lz[k])
        all_apply(2 * k + 1, lz[k])
        lz[k] = id_x

    def build(arr):
        assert len(arr) == n
        for j in range(n):
            d[size + j] = arr[j]
        for j in range(size - 1, 0, -1):
            update(j)

    def all_prod():
        return d[1]

    def range_apply(l, r, f):
        assert 0 <= l <= r <= n
        if l == r:
            return
        l += size
        r += size
        for i in range(log, 0, -1):
            if ((l >> i) << i) != l:
                push(l >> i)
            if ((r >> i) << i) != r:
                push((r - 1) >> i)
        l2 = l
        r2 = r
        while l < r:
            if l & 1:
                all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                all_apply(r, f)
            l >>= 1
            r >>= 1
        l = l2
        r = r2
        for i in range(1, log + 1):
            if ((l >> i) << i) != l:
                update(l >> i)
            if ((r >> i) << i) != r:
                update((r - 1) >> i)
	
    q = inp[1]
    X = inp[2::3]
    Y = inp[3::3]
    REP = inp[4::3]
    A = np.zeros(n, dtype=np.int64)
    tmp = 1
    for i in range(n - 1, -1, -1):
        A[i] = (tmp << 32) + tmp
        tmp *= 10
        tmp %= MOD

    build(A)

    ans = np.zeros(q, dtype=np.int64)
    for i in range(q):
        range_apply(X[i] - 1, Y[i], REP[i])
        ans[i] = all_prod() >> 32

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

from my_module import solve

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

class SegmentTree():
    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.propagate_above(i)
        self.X[i] = x
        self.A[i] = unitA
        self.calc_above(i)
    
    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)
    
    def check(self, randX, randA, maxs, rep):
        from random import randrange
        for _ in range(rep):
            x = randX()
            y = randX()
            z = randX()
            a = randA()
            b = randA()
            c = randA()
            s = randrange(1, maxs + 1)
            t = randrange(1, maxs + 1)
            err = 0
            if not f(x, unitX) == f(unitX, x) == x:
                err = 1
                print("!!!!! unitX Error !!!!!")
                print("unitX =", unitX)
                print("x =", x)
                print("f(x, unitX) =", f(x, unitX))
                print("f(unitX, x) =", f(unitX, x))
            
            if not h(a, unitA) == h(unitA, a) == a:
                err = 1
                print("!!!!! unitA Error !!!!!")
                print("unitA =", unitA)
                print("a =", a)
                print("f(a, unitA) =", f(a, unitA))
                print("f(unitA, a) =", f(unitA, a))
                
            if not f(f(x, y), z) == f(x, f(y, z)):
                err = 1
                print("!!!!! Associativity Error X !!!!!")
                print("x, y, z, f(x, y), f(y, x) =", x, y, z, f(x, y), f(y, x))
                print("f(f(x, y), z) =", f(f(x, y), z))
                print("f(x, f(y, z)) =", f(x, f(y, z)))
            
            if not h(h(a, b), c) == h(a, h(b, c)):
                err = 1
                print("!!!!! Associativity Error A !!!!!")
                print("a, b, c, h(a, b), h(b, c) =", a, b, c, h(a, b), h(b, c))
                print("h(h(a, b), c) =", h(h(a, b), c))
                print("h(a, h(b, c)) =", h(a, h(b, c)))
            
            if not g(x, unitA, s) == x:
                err = 1
                print("!!!!! Identity Error !!!!!")
                print("unitA, x, s =", unitA, x, s)
                print("g(x, unitA, s) =", g(x, unitA, s))
            
            if not g(g(x, a, s), b, s) == g(x, h(a, b), s):
                err = 1
                print("!!!!! Act Error 1 !!!!!")
                print("x, a, b, s, g(x, a, s), h(a, b) =", x, a, b, s, g(x, a, s), h(a, b))
                print("g(g(x, a, s), b, s) =", g(g(x, a, s), b, s))
                print("g(x, h(a, b), s)    =", g(x, h(a, b), s))
            
            if not g(f(x, y), a, s + t) == f(g(x, a, s), g(y, a, t)):
                err = 1
                print("!!!!! Act Error 2 !!!!!")
                print("x, y, a, s, t, f(x, y), g(x, a, s), g(y, a, t) =", x, y, a, s, t, f(x, y), g(x, a, s), g(y, a, t))
                print("g(f(x, y), a, s + t)      =", g(f(x, y), a, s + t))
                print("f(g(x, a, s), g(y, a, t)) =", f(g(x, a, s), g(y, a, t)))
            
            if err:
                break
                assert f(x, unitX) == f(unitX, x) == x
                assert h(a, unitA) == h(unitA, a) == a
                assert f(f(x, y), z) == f(x, f(y, z))
                assert h(h(a, b), c) == h(a, h(b, c))
                assert g(x, unitA, s) == x
                assert g(g(x, a, s), b, s) == g(x, h(a, b), s)
                assert g(f(x, y), a, s + t) == f(g(x, a, s), g(y, a, t))
        else:
            pass
            print("Monoid Check OK!")
    
    def debug1(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")
    
    def debug(self, k = 10):
        print("--- debug ---")
        print("point")
        for i in range(min(self.n - 1, k)):
            print(i, self.getvalue(i))
        print("prod")
        for i in range(min(self.n, k)):
            print(i, self.getrange(0, i))
        print("--- ---")


# ↓和を使うときはこっちの方が少し高速
# from operator import add
# f = lambda a, b: (a[0] * b[0] % P, (a[1] * b[0] + b[1]) % P) # 1次関数の合成


P = 998244353
inv9 = 443664157
mm = (1 << 18) - 1

def f(x, y):
    # print("f", x, y)
    l1, su1 = x & mm, x >> 18
    l2, su2 = y & mm, y >> 18
    return (((su1 + su2) % P) << 18) + l1

def g(x, a, s):
    l, su = x & mm, x >> 18
    return (((po10[s] - 1) * inv9 % P * po10[l] * a % P) << 18) + l if a else x
    
h = lambda a, b: b if b else a

unitX = 0
unitA = 0
N, Q = map(int, input().split())
x = 1
X = []
po10 = []
for i in range(N):
    X.append((x << 18) + i)
    po10.append(x)
    x = x * 10 % P
po10.append(x)

st = SegmentTree(X, unitX, unitA, f, g, h)

if False:
    from random import randrange
    randX = lambda: (randrange(-10, 11), randrange(-10, 11))
    randA = lambda: ["", "A", "B"][randrange(3)]
    maxs = 10
    rep = 1000
    st.check(randX, randA, maxs, rep)

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