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:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

#########################################################################################################

from itertools import accumulate
import sys
input = sys.stdin.readline

MOD = 998244353
off = 22
mask = 1<<22

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

P = [pow(10,p,MOD) for p in range(N+1)]
SP = [0]
for p in P:
    SP.append((SP[-1]+p)%MOD)
# クエリ関数
ef = 0


def f(x, y):
    x0, x1 = divmod(x, 1 << off)
    y0, y1 = divmod(y, 1 << off)
    res = x0 * P[y1] + y0
    res %= MOD
    return (res << off) + x1 + y1


# merge関数
eh = -1


def h(a, b):
    return a if a != eh else b


# 更新関数（g が局所的か要確認
def g(a, x):
    x1 = x % mask
    return a * (SP[x1] << off) + x1


st = LazySegmentTree(N, f, g, h, ef, eh)

st.built([(1 << off) + 1] * N)
for _ in range(Q):
    L, R, D = map(int, input().split())
    st.update_range(L - 1, R, D)
    print((st.get_range(0, N) >> off) % MOD)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

MOD = 998244353

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

e = 0
id_x = -1


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


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


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(1, size)[::-1]:
        update(j)


def set(p, x):
    assert 0 <= p < n
    p += size
    for i in range(1, log + 1)[::-1]:
        push(p >> i)
    d[p] = x
    for i in range(1, log + 1):
        update(p >> i)


def get(p):
    assert 0 <= p < n
    p += size
    for i in range(1, log + 1):
        push(p >> i)
    return d[p]


def prod(l, r):
    assert 0 <= l <= r <= n
    if l == r:
        return e
    l += size
    r += size
    for i in range(1, log + 1)[::-1]:
        if ((l >> i) << i) != l:
            push(l >> i)
        if ((r >> i) << i) != r:
            push(r >> i)
    sml = smr = e
    while l < r:
        if l & 1:
            sml = op(sml, d[l])
            l += 1
        if r & 1:
            r -= 1
            smr = op(d[r], smr)
        l >>= 1
        r >>= 1
    return op(sml, smr)


def all_prod():
    return d[1]


def apply(p, f):
    assert 0 <= p < n
    p += size
    for i in range(1, log + 1)[::-1]:
        push(p >> i)
    d[p] = mapping(f, d[p])
    for i in range(1, log + 1):
        update(p >> i)


def range_apply(l, r, f):
    assert 0 <= l <= r <= n
    if l == r:
        return
    l += size
    r += size
    for i in range(1, log + 1)[::-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)


def max_right(l, g):
    assert 0 <= l <= n
    # assert g(e)
    if l == n:
        return n
    l += size
    for i in range(1, log + 1)[::-1]:
        push(l >> i)
    sm = e
    while True:
        while l % 2 == 0:
            l >>= 1
        if not g(op(sm, d[l])):
            while l < size:
                push(l)
                l = 2 * l
                if g(op(sm, d[l])):
                    sm = op(sm, d[l])
                    l += 1
            return l - size
        sm = op(sm, d[l])
        l += 1
        if (l & -l) == l:
            return n


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


n, q = map(int, input().split())
log = (n - 1).bit_length()
size = 1 << log
d = [e] * (2 * size)
lz = [id_x] * size

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

build(A)

ans = [0] * q
for i in range(q):
    x, y, rep = map(int, input().split())
    range_apply(x - 1, y, rep)
    ans[i] = all_prod() >> 32

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

Submission status: Accepted

Solution code:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

#########################################################################################################

from itertools import accumulate
import sys
input = sys.stdin.readline

MOD = 998244353
off = 22
mask = 1<<22

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

P = [pow(10,p,MOD) for p in range(N+1)]
SP = [0]+list(accumulate(P))
# クエリ関数
ef = 0
def f(x, y):
    x0, x1 = divmod(x,1<<off)
    y0, y1 = divmod(y,1<<off)
    res = x0*P[y1]+y0
    res %= MOD
    return (res<<off) + x1+y1
# merge関数
eh = -1
def h(a,b):
    return a if a != eh else b
# 更新関数（g が局所的か要確認
def g(a, x):
    x1 = x%mask
    res = a*SP[x1]%MOD
    return (res<<off) + x1

st = LazySegmentTree(N, f, g, h, ef, eh)

st.built([(1<<off) + 1]*N)
res = [""]*Q
for i in range(Q):
    L, R, D = map(int, input().split())
    st.update_range(L-1, R, D)
    res[i] = str((st.get_range(0,N)>>off)%MOD)
print("\n".join(res))

Submission status: Accepted

Solution code:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

#########################################################################################################

from itertools import accumulate
import sys
input = sys.stdin.readline

MOD = 998244353
off = 22
mask = 1<<22

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

P = [pow(10,p,MOD) for p in range(N+1)]
SP = [0]
for p in P:
    SP.append((SP[-1]+p)%MOD)
# クエリ関数
ef = 0
def f(x, y):
    x0, x1 = divmod(x,1<<off)
    y0, y1 = divmod(y,1<<off)
    res = x0*P[y1]+y0
    res %= MOD
    return (res<<off) + x1+y1
# merge関数
eh = -1
def h(a,b):
    return a if a != eh else b
# 更新関数（g が局所的か要確認
def g(a, x):
    x1 = x%mask
    return a*(SP[x1]<<off) + x1

st = LazySegmentTree(N, f, g, h, ef, eh)

st.built([(1<<off) + 1]*N)
res = [""]*Q
for i in range(Q):
    L, R, D = map(int, input().split())
    st.update_range(L-1, R, D)
    res[i] = str((st.get_range(0,N)>>off)%MOD)
print("\n".join(res))