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:
import sys
input = sys.stdin.buffer.readline

MOD = 998244353
INF = 2 * 10**18

in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]


# ----- seg tree設定 ----- #

e = 0
id = -1
MASK = 32


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


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


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

# ----- seg tree設定 ここまで ----- #


class LazySegmentTree():
    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.d = [e] * (2 * self.size)
        self.lz = [id] * (self.size)

    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.id

    def build(self, arr):
        # assert len(arr) == self.n
        for i in range(self.n):
            self.d[self.size + i] = arr[i]
        for i in range(1, self.size)[::-1]:
            self.update(i)

    def set(self, p, x):
        # assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-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):
        # assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        # assert 0 <= l <= r <= self.n
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-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.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 all_prod(self):
        return self.d[1]

    def apply(self, p, f):
        # assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-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)

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

    def min_left(self, r, g):
        # assert 0 <= r <= self.n
        # assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(1, self.log + 1)[::-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.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r:
                return 0


def main():

    N, Q = in_nn()

    A = [0] * N
    tmp = 1
    for i in range(N - 1, -1, -1):
        A[i] = (tmp << MASK) + tmp
        tmp *= 10
        tmp %= MOD

    seg = LazySegmentTree(N, op, e, mapping, composition, id)
    seg.build(A)

    ans = [0] * Q
    for i in range(Q):
        l, r, d = in_nn()
        l -= 1
        seg.range_apply(l, r, d)
        ans[i] = seg.all_prod() >> MASK

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class LazySegmentTree:
    # 0-indexed
    # 2^m
    # ref. https://yukicoder.me/submissions/470340
    def __init__(self, length, op=min, e=lambda: 0, act=lambda f, x: f if f != 0 else x, composition=lambda f, g: g, idf=lambda: 0):
        """
        :param length: length of initial values
        :param op: operator, op(x, y) -> z
        :param e: function that return identity element for op
        """
        self.op = op
        self.e = e
        self.act = act
        self.composition = composition
        self.n = 1
        self.idf = idf
        while self.n < length:
            self.n *= 2  # pow2
        self.dat_v = [self.e()] * (2 * self.n - 1)
        self.dat_f = [self.idf()] * (2 * self.n - 1)

    def initialize(self, x_list):
        """
        initialize data
        :param x_list: initial values fot list
        :return:
        """
        assert len(x_list) <= self.n
        # update base
        # ith -> n - 1 + i
        for i, x in enumerate(x_list):
            self.dat_v[self.n - 1 + i] = x
        # upper values
        for i in range(self.n - 2, -1, -1):
            self.dat_v[i] = self.op(self.dat_v[2 * i + 1], self.dat_v[2 * i + 2])

    def _eval_at(self, i):
        return self.act(self.dat_f[i], self.dat_v[i])

    def _propagate_at(self, i):
        self.dat_v[i] = self._eval_at(i)
        self.dat_f[i * 2 + 1] = self.composition(self.dat_f[i * 2 + 1], self.dat_f[i])
        self.dat_f[i * 2 + 2] = self.composition(self.dat_f[i * 2 + 2], self.dat_f[i])
        self.dat_f[i] = self.idf()

    def _propagate_above(self, i):
        history = []
        while i > 0:
            i = (i - 1) // 2
            history.append(i)
        for j in reversed(history):
            self._propagate_at(j)

    def _re_calculate_above(self, i):
        while i > 0:
            i = (i - 1) // 2
            self.dat_v[i] = self.op(self._eval_at(2 * i + 1), self._eval_at(2 * i + 2))

    def operate_range(self, p, q, f):
        """
        apply operator f for [p, q)
        :param p: int
        :param q: int
        :param f: operator
        :return: None
        """
        if p >= q:
            return None
        p0 = p + self.n - 1
        q0 = q + self.n - 2
        # propagate from top
        self._propagate_above(p0)
        self._propagate_above(q0)
        # compose f
        while q0 - p0 > 1:
            if p0 & 1 == 0:
                self.dat_f[p0] = self.composition(self.dat_f[p0], f)
            if q0 & 1 == 1:
                self.dat_f[q0] = self.composition(self.dat_f[q0], f)
                q0 -= 1
            p0 = p0 // 2
            q0 = (q0 - 1) // 2
        if p0 == q0:
            self.dat_f[p0] = self.composition(self.dat_f[p0], f)
        elif p0 & 1 == 1:
            self.dat_f[p0 // 2] = self.composition(self.dat_f[p0 // 2], f)
        else:
            self.dat_f[p0] = self.composition(self.dat_f[p0], f)
            self.dat_f[q0] = self.composition(self.dat_f[q0], f)
        # re-calculate above
        self._re_calculate_above(p + self.n - 1)
        self._re_calculate_above(q + self.n - 2)

    def set_val(self, k, v):
        """
        update k-th(0-indexed) value with v
        :param k: index to set(0-indexed)
        :param v: value to set
        :return: None
        """
        k += self.n - 1
        self.dat_v[k] = v
        self.dat_f[k] = self.idf()
        self._re_calculate_above(k)

    def query(self, p, q):
        """
        :param p: int
        :param q: int
        :return: "minimum" value in [p, q)
        """
        if q <= p:
            return self.e()
        p0 = p + self.n - 1
        q0 = q + self.n - 2
        self._propagate_above(p0)
        self._propagate_above(q0)
        vl = self.e()
        vr = self.e()
        while q0 - p0 > 1:
            if p0 & 1 == 0:
                vl = self.op(vl, self._eval_at(p0))
            if q0 & 1 == 1:
                vr = self.op(self._eval_at(q0), vr)
                q0 -= 1
            p0 = p0 // 2
            q0 = (q0 - 1) // 2
        if p0 == q0:
            res = self.op(self.op(vl, self._eval_at(p0)), vr)
        else:
            res = self.op(self.op(vl, self._eval_at(p0)), self.op(self._eval_at(q0), vr))
        return res


MOD = 998244353
MOD_INV_9 = pow(9, MOD - 2, MOD)


def op_con(x, y):
    if y[1] == 0:
        return x
    elif x[1] == 0:
        return y
    else:
        return (x[0] * y[1] + y[0]) % MOD, (x[1] * y[1]) % MOD


def e_zero():
    return 0, 0


def act_change(f, x):
    if f == 0:
        return x
    else:
        return ((x[1] - 1) * MOD_INV_9 * f) % MOD, x[1]


def com_change(f, g):
    if g == 0:
        return f
    else:
        return g


def idf_change():
    return 0


def solve(n, q, lrd_list):

    lsq = LazySegmentTree(n, op_con, e_zero, act=act_change, composition=com_change, idf=idf_change)
    lsq.initialize([(1, 10)] * n)

    res = []

    for i in range(q):
        l, r, d = lrd_list[i]
        # find where
        lsq.operate_range(l - 1, r, d)
        res.append(lsq.query(0, n)[0])

    return res


def solve_greedy(n, q, lrd_list):
    assert n <= 12 or q <= 10
    rep = [1] * n

    res = []

    for i in range(q):
        l, r, d = lrd_list[i]
        for j in range(l - 1, r):
            rep[j] = d
        res.append(int("".join([str(k) for k in rep])) % MOD)

    return res


def main():
    n, q = map(int, input().split())
    lrd_list = [tuple(map(int, input().split())) for _ in range(q)]
    res = solve(n, q, lrd_list)
    for r in res:
        print(r)


def test():
    assert solve(8, 5, [(3, 6, 2), (1, 4, 7), (3, 8, 3), (2, 2, 2), (4, 5, 1)]) == [11222211, 77772211, 77333333,
                                                                                    72333333, 72311333]
    assert solve(200000, 1, [(123, 456, 7)]) == [641437905]
    assert solve_greedy(8, 5, [(3, 6, 2), (1, 4, 7), (3, 8, 3), (2, 2, 2), (4, 5, 1)]) == [11222211, 77772211, 77333333,
                                                                                    72333333, 72311333]
    assert solve_greedy(200000, 1, [(123, 456, 7)]) == [641437905]
    assert solve_greedy(12, 1, [(4, 9, 3)]) == solve(12, 1, [(4, 9, 3)])


def test_random():
    import random
    for i in range(10):
        rand_list = []
        for _ in range(5):
            p = random.choice(list(range(12))) + 1
            q = random.choice(list(range(12))) + 1
            p, q = min(p, q), max(p, q)
            r = random.choice(list(range(9))) + 1
            rand_list.append((p, q, r))
        if solve(12, 5, rand_list) == solve_greedy(12, 5, rand_list):
            print("pass", i + 1)
        else:
            print(rand_list, solve(12, 5, rand_list), solve_greedy(12, 5, rand_list))


def test_493():
    n = 12
    lsq = LazySegmentTree(n, op_con, e_zero, act=act_change, composition=com_change, idf=idf_change)
    lsq.initialize([(1, 10)] * n)
    print(lsq.n)
    print(lsq.dat_f, lsq.dat_v)
    l, r, d = 4, 9, 3
    # find where
    lsq.operate_range(l - 1, r, d)
    print(lsq.dat_f, lsq.dat_v)
    print(lsq.query(0, 8)[0], lsq.query(8, 12)[0])
    print(lsq.dat_f, lsq.dat_v)


if __name__ == "__main__":
    # test_493()
    test()
    # test_random()
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### 遅延評価セグメント木
class LazySegmentTree:
    def __init__(self, n, a=None):
        """初期化
        num : n以上の最小の2のべき乗
        """
        num = 1
        while num<=n:
            num *= 2
        self.num = num
        self.seg = [ninf] * (2*self.num-1)
        self.lazy = [f0] * (2*self.num-1)
        self.ls = [0]*(2*self.num-1)
        self.rs = [0]*(2*self.num-1)
        self.ls[0] = 0
        self.rs[0] = self.num
        for i in range(self.num-1):
            self.ls[2*i+1] = self.ls[i]
            self.rs[2*i+1] = (self.ls[i] + self.rs[i])//2
            self.ls[2*i+2] = (self.ls[i] + self.rs[i])//2
            self.rs[2*i+2] = self.rs[i]
        if a is not None:
            # O(n)で初期化
            assert len(a)==n
            for i in range(n):
                self.seg[num-1+i] = a[i]
            for k in range(num-2, -1, -1):
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def eval(self, k):
        if self.lazy[k]==f0:
            return 
        if k<self.num-1:
            self.lazy[k*2+1] = composition(self.lazy[k], self.lazy[k*2+1])
            self.lazy[k*2+2] = composition(self.lazy[k], self.lazy[k*2+2])
        self.seg[k] = mapping(self.lazy[k], self.seg[k])
        self.lazy[k] = f0
    def eval_all(self):
        for i in range(2*self.num-1):
            self.eval(i)
    def update(self,a,b,x=None,f=None):
        """A[a]...A[b-1]をxに更新する
        """
        if f is None:
            # 更新クエリ
            f = lambda y: x
        k = 0
        q = [k] # k>=0なら行きがけ順
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            if k>=0:
                self.eval(k)
                if r<=a or b<=l:
                    continue
                elif a<=l and r<=b:
                    self.lazy[k] = composition(f, self.lazy[k])
                    self.eval(k)
                else:
                    q.append(~k)
                    q.append(2*k+1)
                    q.append(2*k+2)
            else:
                k = ~k
                self.seg[k] = op(self.seg[2*k+1], self.seg[2*k+2])
    def query(self,a,b):
        k = 0
        l = 0
        r = self.num
        q = [k]
        ans = ninf
        # 重なる区間を深さ優先探索
        while q:
            k = q.pop()
            l,r = self.ls[k], self.rs[k]
            self.eval(k)
            if r<=a or b<=l:
                continue
            elif a<=l and r<=b:
                ans = op(ans, self.seg[k])
            else:
                q.append(2*k+2)
                q.append(2*k+1)
#             print(q, ans, l,r,a,b, self.seg[k])
        return ans

n,q = list(map(int, input().split()))
M = 998244353
vals = [1]
vals2 = [1]
v = 1
for i in range(n):
    v *= 10
    v %= M
    vals.append(v)
    vals2.append((1+vals2[-1]*10)%M)
    
ninf = 0 # (転倒数, #0, #1)
V = (1<<32)
def op(x,y):
#     print(x,bin(y))
    return ((x%V)*vals[y//V] + y%V)%M + (x//V + y//V)*V
# op = lambda x,y: ((x[0]*vals[y[1]] + y[0])%M, x[1]+y[1])
# op = lambda x,y: ((x[0]*vals[y[1]] + y[0])%M, x[1]+y[1])

mapping = lambda f,x: x if f is None else ((f%10)*vals2[(x//V)-1])%M + (x//V)*V
def composition(f1,f2):
    if f1 is None:
        return f2
    else:
        return f1
#     elif f2 is None:
#         return f1
#     else:
#         if f1//10<f2//10:
#             return f2
#         else:
#             return f1
# composition = lambda f1, f2: f1 if f2 is None else 
f0 = None
sg = LazySegmentTree(n, [1+(1<<32)]*n)
ans = [None]*q
for i in range(q):
    l,r,d = map(int, input().split())
    l -= 1
    r -= 1
#     print(l,r,d)
    sg.update(l,r+1,f=10*i+d)
    ans[i] = sg.query(0,n+1)%V
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
LRD = [tuple(map(int,input().split())) for i in range(Q)]
MOD = 998244353

class LazySegTree:
    def __init__(self, op, e, mapping, composition, _id, arr=[]):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = _id
        self.n = len(arr)
        self.log = self._ceil_pow2(self.n)
        self.size = 1 << self.log
        self.d = [e()] * (2*self.size)
        self.lz = [_id()] * self.size
        for i in range(self.n):
            self.d[self.size + i] = arr[i]
        for i in range(self.size-1, 0, -1):
            self._update(i)

    def _ceil_pow2(self, n):
        assert n >= 0
        x = 0
        while (1<<x) < n:
            x += 1
        return x

    def set(self, p, x):
        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):
        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, l, r):
        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()
        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 all_prod(self):
        return self.d[1]

    def apply(self, p, f):
        assert 0 <= p < 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)

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

        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.id()

inv9 = pow(9,MOD-2,MOD)
def op(l,r):
    lx,lw = l
    rx,rw = r
    return ((lx*rw + rx)%MOD, (lw*rw)%MOD)
def e():
    return (0,1)
def mapping(l,r):
    if l==0: return r
    rx,rw = r
    return (((rw-1)*inv9*l)%MOD, rw)
def composition(l,r):
    return r if l==0 else l
def _id():
    return 0

segt = LazySegTree(op, e, mapping, composition, _id, [(1,10) for i in range(N)])
ans = []
for l,r,d in LRD:
    l -= 1
    segt.apply_lr(l,r,d)
    ans.append(segt.all_prod()[0])
print(*ans, sep='\n')

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class LazySegmentTree:
        
        __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
    
        def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
            self.me = monoid_identity
            self.oe = operator_identity
            self.fmm = func_monoid_monoid
            self.fmo = func_monoid_operator
            self.foo = func_operator_operator
    
            self.n = len(monoid_data)
            self.data = monoid_data * 2
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
            
    
        def replace(self, index, value):
            index += self.n
    
            # propagation
            for shift in range(index.bit_length()-1, 0, -1):
                i = index >> shift
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # update
            self.data[index] = value
            self.lazy[index] = self.oe
    
            # recalculation
            i = index
            while i > 1:
                i //= 2
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
    
    
        def effect(self, l, r, operator):
            l += self.n
            r += self.n
            
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
    
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # effect
            while l < r:
                if l % 2:
                    self.lazy[l] = self.foo(self.lazy[l], operator)
                    l += 1
                if r % 2:
                    r -= 1
                    self.lazy[r] = self.foo(self.lazy[r], operator)
                l //= 2
                r //= 2
    
            # recalculation
            for i in indices:
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
                
            
        def folded(self, l, r):
            l += self.n
            r += self.n
    
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
            
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # fold
            left_folded = self.me
            right_folded = self.me
            while l < r:
                if l % 2:
                    left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                    l += 1
                if r % 2:
                    r -= 1
                    right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
                l //= 2
                r //= 2
            return self.fmm(left_folded, right_folded)


    mod=998244353
    N,Q=MI()
    
    POW=[1]
    for _ in range(N+5):
        a=POW[-1]
        a*=10
        a%=mod
        POW.append(a)
        
    inv9=pow(9,mod-2,mod)#9でわる
        
    MM=32
    mask=(1<<MM)-1
    # (数，今見てる数の桁数)を1つにまとめる
    def enc(a,d):
        return (a<<MM) + d
    
    def dec(v):
        a=v>>MM
        d=v&mask
        return a,d
    
    mide=enc(1,1)
    monoid_data=[mide]*N

        
    monoid_ide=0#0を足したいからこれで
    ope_ide=0
    
    def fmm(m1,m2):
        # print(m1,m2)
        a1,d1=dec(m1)
        a2,d2=dec(m2)
        
        # print(a1,d1,a2,d2)
        
        temp=a1*POW[d2]+a2
        
        return enc(temp%mod,d1+d2)#桁数は足せば良い
    
    def fmo(m1,o1):
        if o1:
            # o1がd1桁だけ続くものを返したい
            a1,d1=dec(m1)
            
            temp=(o1*(POW[d1]-1)*inv9)#1がd1桁
            return enc(temp%mod,d1)
        else:
            return m1
    
    def foo(o1,o2):
        if o2:
            return o2
        else:
            return o1
    
    Lseg=LazySegmentTree(monoid_data,monoid_ide,ope_ide,fmm,fmo,foo)
    
    for _ in range(Q):
        # print("---")
        l,r,d=MI()
        l-=1
        r-=1
        Lseg.effect(l,r+1,d)
        ans=Lseg.folded(0,N)
        a,d=dec(ans)
        print(a)
    
    
    

        



main()