Problem:


Score : 500 points

Problem Statement

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

You will perform queries Q times.
In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit).
Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

1 \leq N, Q \leq 200,000

1 \leq L_i \leq R_i \leq N

1 \leq D_i \leq 9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q

Output

Print Q lines.
In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Sample Input 1

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

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.



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


Sample output:
11222211
77772211
77333333
72333333
72311333

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

#Ref[0] = 1
#for s in range(1,P.bit_length()):
#    Ref[s] += (Ref[s-1] * (pow_10_MOD[pow_2_lv[s-1]] + 1)) % MOD
#    Ref[s] %= MOD

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

#####segfunc#####
def segfunc(x, y):
    xa, xb = x
    ya, yb = y
    return [(xa + ya) % MOD, (xb + yb) % MOD]
#################

#####triv_act#####
triv_act = 0
#################

#####action#####
def action(x, p):
    if p != triv_act:
      _, xb = x
      return [(xb * p) % MOD , xb]
    return x
#################

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, action, triv_act):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        action: モノイドへの作用
        ide_ele: 単位元
        triv_act: モノイドへ自明に作用する元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.action = action
        self.ide_ele = ide_ele
        self.triv_act = triv_act
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [triv_act] * 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)) >> 1
            rm = (r // (r & -r)) >> 1

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

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v == triv_act:
                continue
            lg = self.data[2 * i][1].bit_length()-1
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = action(self.data[2 * i], v)
            self.data[2 * i + 1] = action(self.data[2 * i + 1], v)
            self.lazy[i] = self.triv_act

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = action(self.data[l], x)
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = action(self.data[r - 1], x)
            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_l = self.ide_ele
        res_r = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res_l = self.segfunc(res_l, self.data[l])
                l += 1
            if r & 1:
                res_r = self.segfunc(self.data[r - 1], res_r)
            l >>= 1
            r >>= 1
        return self.segfunc(res_l, res_r)      
      
import sys
input = sys.stdin.buffer.readline

N, Q = map(int,input().split()) #3*10**5+5, 10**5 
init = [[1,1] for _ in range(N)]

tmp = 1
for i in range(N-2,-1,-1):
  tmp = (tmp * 10) % MOD
  init[i][0], init[i][1] = tmp, tmp
lst = LazySegmentTree(init, segfunc, ide_ele, action, triv_act)
#print(lst.data[1], lst.data)

ans = [0 for _ in range(Q)]
for i in range(Q):
  L, R, D = map(int,input().split()) #i, N//2+1, i*4 % 9 + 1
  L -= 1
  R -= 1
  lst.update(L, R+1, D)
  #print(lst.data[1], lst.data)
  ans[i] = lst.data[1][0]
print(*ans, sep="\n")
#print(lst.data)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

#Ref[0] = 1
#for s in range(1,P.bit_length()):
#    Ref[s] += (Ref[s-1] * (pow_10_MOD[pow_2_lv[s-1]] + 1)) % MOD
#    Ref[s] %= MOD

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

#####segfunc#####
def segfunc(x, y):
    xa, xb = x
    ya, yb = y
    return [(xa + ya) % MOD, (xb + yb) % MOD]
#################

#####triv_act#####
triv_act = 0
#################

#####action#####
def action(x, p):
    if p != triv_act:
      _, xb = x
      return [(xb * p) % MOD , xb]
    return x
#################

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, action, triv_act):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        action: モノイドへの作用
        ide_ele: 単位元
        triv_act: モノイドへ自明に作用する元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.action = action
        self.ide_ele = ide_ele
        self.triv_act = triv_act
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [triv_act] * 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)) >> 1
            rm = (r // (r & -r)) >> 1

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

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v == triv_act:
                continue
            lg = self.data[2 * i][1].bit_length()-1
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = action(self.data[2 * i], v)
            self.data[2 * i + 1] = action(self.data[2 * i + 1], v)
            self.lazy[i] = self.triv_act

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = action(self.data[l], x)
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = action(self.data[r - 1], x)
            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_l = self.ide_ele
        res_r = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res_l = self.segfunc(res_l, self.data[l])
                l += 1
            if r & 1:
                res_r = self.segfunc(self.data[r - 1], res_r)
            l >>= 1
            r >>= 1
        return self.segfunc(res_l, res_r)      
      
import sys
input = sys.stdin.buffer.readline

N, Q = map(int,input().split()) #3*10**5+5, 10**5 
init = [[1,1] for _ in range(N)]

tmp = 1
for i in range(N-2,-1,-1):
  tmp = (tmp * 10) % MOD
  init[i][0], init[i][1] = tmp, tmp
lst = LazySegmentTree(init, segfunc, ide_ele, action, triv_act)
#print(lst.data[1], lst.data)

for i in range(Q):
  L, R, D = map(int,input().split()) #i, N//2+1, i*4 % 9 + 1
  L -= 1
  R -= 1
  lst.update(L, R+1, D)
  #print(lst.data[1], lst.data)
  print(lst.data[1][0])
#print(lst.data)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

#Ref[0] = 1
#for s in range(1,P.bit_length()):
#    Ref[s] += (Ref[s-1] * (pow_10_MOD[pow_2_lv[s-1]] + 1)) % MOD
#    Ref[s] %= MOD

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

#####segfunc#####
def segfunc(x, y):
    xa, xb = x
    ya, yb = y
    return [(xa + ya) % MOD, (xb + yb) % MOD]
#################

#####triv_act#####
triv_act = 0
#################

#####action#####
def action(x, p):
    if p != triv_act:
      _, xb = x
      return [(xb * p) % MOD , xb]
    return x
#################

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, action, triv_act):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        action: モノイドへの作用
        ide_ele: 単位元
        triv_act: モノイドへ自明に作用する元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.action = action
        self.ide_ele = ide_ele
        self.triv_act = triv_act
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [triv_act] * 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)) >> 1
            rm = (r // (r & -r)) >> 1

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

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v == triv_act:
                continue
            lg = self.data[2 * i][1].bit_length()-1
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = action(self.data[2 * i], v)
            self.data[2 * i + 1] = action(self.data[2 * i + 1], v)
            self.lazy[i] = self.triv_act

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = action(self.data[l], x)
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = action(self.data[r - 1], x)
            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_l = self.ide_ele
        res_r = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res_l = self.segfunc(res_l, self.data[l])
                l += 1
            if r & 1:
                res_r = self.segfunc(self.data[r - 1], res_r)
            l >>= 1
            r >>= 1
        return self.segfunc(res_l, res_r)      
      
import sys
input = sys.stdin.readline

N, Q = map(int,input().split()) #3*10**5+5, 10**5 
init = [[1,1] for _ in range(N)]

tmp = 1
for i in range(N-2,-1,-1):
  tmp = (tmp * 10) % MOD
  init[i][0], init[i][1] = tmp, tmp
lst = LazySegmentTree(init, segfunc, ide_ele, action, triv_act)
#print(lst.data[1], lst.data)

for i in range(Q):
  L, R, D = map(int,input().split()) #i, N//2+1, i*4 % 9 + 1
  L -= 1
  R -= 1
  lst.update(L, R+1, D)
  #print(lst.data[1], lst.data)
  print(lst.data[1][0])
#print(lst.data)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

mod = 998244353
n,q = map(int,input().split())
l=[0]*q
r=[0]*q
d=[0]*q
for i in range(q):
    l[i],r[i],d[i]=map(int,input().split())


s = np.array([1]*n)
for i in range(q):
    s[l[i]-1:r[i]] = d[i]
    ans = ''
    for j in range(n):
        ans += str(s[j])
    print(int(ans)%mod)

Submission status: Time Limit Exceeded

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))
# クエリ関数
ef = 0
def f(x, y):
    x0, x1 = divmod(x,1<<off)
    y0, y1 = divmod(y,1<<off)
    res = x0*P[y1]+y0
    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: Time Limit Exceeded

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
    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)