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:
N, Q, *LRD = [int(_) for _ in open(0).read().split()]
L, R, D = LRD[::3], LRD[1::3], LRD[2::3]
mod = 998244353


class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def reflect(self, k):
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])

    def evaluate(self, k):
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei

    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)

    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))

    def update(self, a, b, x):  # set value at position [a, b) (0-indexed)
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)

    def set_val(self, a, x):
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)

    def query(self, a, b):  # result on interval [a, b) (0-indexed)
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


#RSQ and RUQ
array = [(pow(10, i, mod), pow(10, i, mod), 1) for i in range(N)][::-1]
f = lambda a, b: ((a[0] + b[0]) % mod, (a[1] + b[1]) % mod, a[2] + b[2])
g = lambda a, b: (b * a[1] % mod, a[1], a[2])
h = lambda a, b: b
ti = (0, 0, 0)
ei = -float('inf')

lst = LazySegmentTree(array=array, ti=ti, ei=ei, f=f, g=g, h=h)
ans = []
for l, r, d in zip(L, R, D):
    lst.update(l - 1, r, d)
    ans += [lst.query(0, N)[0]]
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = "1" * N
As = []
for _ in range(Q):
  L, R, D = map(int, input().split())
  S = list(S)
  S[L - 1 : R] = str(D) * (R - L + 1)
  S = ''.join(S)
  print(int(S) % 998_244_353)

Submission status: Time Limit Exceeded

Solution code:
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)

N,Q=map(int,input().split())
l,r,d=0,0,0
mod=998244353
inv9=pow(9,mod-2,mod)
def f(x,y):
  if x==(0,0):
    return y
  if y==(0,0):
    return x
  return ((x[0]*pow(10,y[1],mod)+y[0])%mod,x[1]+y[1])

def g(x,y):
  if y!=-1:
    return ((pow(10,x[1],mod)-1)*y*inv9%mod,x[1])
  else:
    return x

def h(x,y):
  if y==-1 and x!=-1:
    return x
  return y

n=1
while n<N:
  n<<=1
Y=n-N
X=LazySegmentTree([(0,1) if i<Y else (1,1) for i in range(n)],(0,0),-1,f,g,h)
for i in range(Q):
  l,r,d=map(int,input().split())
  l+=Y-1
  r+=Y
  X.effect(l,r,d)
  print(X.folded(0,n)[0])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lst=[1]*n
while q>0:
    l,r,d=map(int,input().split())
    l-=1
    r-=1
    for i in range(l,r+1):
        lst[i]=d
    x=""
    for ele in lst:
        x=x+str(ele)
    print(int(x)%998244353)
    q-=1

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int, input().split()))
L = []
for _ in range(Q):
    L.append(list(map(int, input().split())))

mod = 998244353

n = [str(1)] * N

for j in range(Q):
    n[L[j][0]-1:L[j][1]] = str(L[j][2])*(L[j][1]-L[j][0]+1)
    print(int(''.join(n))%mod)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
s = '1'*n
m = 998244353
for _ in range(q):
  a,b,c = map(int,input().split())
  s = s[:a-1] + str(c)*((b-a)+1) + s[b:]
  print(int(s)%m)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

s = [1 for i in range(n)]
for i in range(q):
    l, r, d = map(int, input().split())

    for i in range(l - 1, r):
        s[i] = d

    ans = ''.join([str(i) for i in s])
    print(int(ans) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
S='1'*N
MOD=998244353
for q in range(Q):
  l,r,d=map(int,input().split())
  S=S[:l-1]+str(d)*(r-l+1)+S[r:]
  _=int(S)
  print(_%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lrd=[list(map(int,input().split())) for i in range(q)]

MOD = 998244353
s='1'*n

for i in range(q):
  left = lrd[i][0]
  right = lrd[i][1]
  num = lrd[i][2]
  tmp1 = s[:left-1]
  tmp2 = s[right:]
  tmp3 = str(num) * (right-left+1)
  s = tmp1 + tmp3 + tmp2
  print(int(s)%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,q = list(map(int,input().split()))

s = ""
for i in range(n):
    s += "1"

ansList = []

for  i in range(q):
    l,r,d = list(map(int,input().split()))
    t = ""
    for j in range(r - l + 1):
        t += str(d)
    s = s[:l-1] + t + s[r:]
    ansList.append(int(s) % 998244353)

for  i in range(q):
    print(ansList[i])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().rstrip().split())
MOD = 998_244_353
s = ["1"]*n
for i in range(q):
    l, r, d = map(int,input().rstrip().split())
    s[l-1:r]=[str(d)]*(r-l+1)
    ans = int("".join(s)) % MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
mod = 998244353
s = '1' * n
for _ in range(q):
    l, r, d = map(int, input().split())
    s = s[:l - 1] + str(d) * (r - l + 1) + s[r:]
    print(int(s) % mod)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
S = ["1"]*n
m = 998244353
for q in range(q):
    temp = S
    l,r,d = map(int,input().split())
    temp[l-1:r] = str(d)*(r-l+1)
    print(int("".join(temp))%m)

Submission status: Time Limit Exceeded

Solution code:
if __name__=="__main__":
    N,Q=[int(i) for i in input().split()] 
    s='1'*N
    for i in range(Q):
        l,r,d=[int(i) for i in input().split()]
        s=s[:l-1]+str(d)*(r-l+1)+s[r:]
        print(int(s)%998244353)
        Q-=1

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())

x="1"*N
ans=[]

for i in range(Q):
    L,R,D=map(int,input().split())
    D=str(D)
    x=''.join([x[0:L-1],D*(R+1-L),x[R:N]])
    ans.append(x)

for i in ans:
    A=int(i)%998244353
    print(A)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

N, Q = map(int,input().split())
S = ['1'] * N
for _ in range(Q):
    L, R, D = map(int,input().split())
    S[L-1:R] = str(D) * (R - L + 1)
    print(int(''.join(S)) % mod)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
S="1"*N
for _ in range(Q):
    l,r,d=map(int,input().split())

    S=S[:l-1]+str(d)*(r-l+1)+S[r:]
    print(int(S)%998244353)

Submission status: Time Limit Exceeded

Solution code:
if __name__=="__main__":
    N,Q=map(int,input().split())
    s='1'*N
    for i in range(Q):
        l,r,d=map(int,input().split())
        s=s[:l-1]+str(d)*(r-l+1)+s[r:]
        print(int(s)%998244353)
        Q-=1

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
mod = 998244353
a = [1]
for i in range(n - 1):
    a.append(a[-1] * 10 % mod)
a.reverse()
num = "1" * n
num2 = int(num) % mod
for i in range(q):
    l, r, d = map(int, input().split())
    num2 += (int(str(d) * (r - l + 1)) - int(num[l - 1:r])) * a[r - 1]
    num2 %= mod
    print(num2)
    num = num[:l - 1] + str(d) * (r - l + 1) + num[r:]

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
moji = ['0'] + ['1' for i in range(n)]
#print(moji)
for i in range(q):
  l,r,d = map(int,input().split())
  for j in range(l,r+1):
    moji[j] = str(d)
  print(int(''.join(moji))%998244353)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
_mod = 998244353
S = '1'*N
for i in range(Q):
    L, R, D = list(map(int, input().split()))
    S = S[:L-1] + str(D)*(R-L+1) + S[R:]
    print(int(S)%_mod)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
a="1"*N
for _ in range(Q):
    L,R,D=map(int,input().split())
    a=a[:L-1]+str(D)*(R-L+1)+a[R:]
    print(int(a)%998244353)

Submission status: Time Limit Exceeded

Solution code:
# AtCoderのPyPy3環境だとこれが一番速い。

MOD = 998244353
mask32 = (1 << 32) - 1

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
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

        # 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
        i = l0
        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
        i = r0
        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 folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> 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
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> 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

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


import sys
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

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

# 値 << 32 + 長さ
def fmm(m1, m2):
    v1 = m1 >> 32
    l1 = m1 & mask32
    v2 = m2 >> 32
    l2 = m2 & mask32
    v = (v1 * pow(10, l2, MOD) + v2) % MOD
    l = l1 + l2
    return (v << 32) + l

inv9 = pow(9, MOD - 2, MOD)
def fmo(m, o):
    if o == -1:
        return m
    else:
        l = m & mask32
        v = o * (pow(10, l, MOD) - 1) * inv9 % MOD
        return (v << 32) + l

def foo(o1, o2):
    if o2 == -1:
        return o1
    else:
        return o2

lst = LazySegmentTree([(1 << 32) + 1] * N, 0, -1, fmm, fmo, foo)

LRDs = map(int, read().split())
for L, R, D in zip(LRDs, LRDs, LRDs):
    lst.effect(L - 1, R, D)
    print(lst.folded(0, N) >> 32)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s="1"*n
for i in range(q):
  l,r,d=map(int,input().split())
  s=s[:l-1]+str(d)*(r-l+1)+s[r:]
  print(int(s)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s="1"*n
for i in range(q):
    l,r,d=map(int,input().split())
    d=str(d)
    s=s[:l-1]+d*(r-l+1)+s[r:]
    t=int(s)
    print(t%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
lrd = [list(map(int, input().split())) for i in range(q)]
mod = 998244353
s = "1"*n
for i in range(q):
    l, r, d = lrd[i]
    s = s[:l-1] + str(d)*(r-l+1) + s[r:]
    print(int(s)%mod)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
a = [1 for _ in range(n)]
while (q > 0):
    l, r, d = map(int, input().split())
    l -= 1
    while (l != r):
        a[l] = d
        l += 1
    s = 0
    for i in a:
        s = s * 10 + i
    print(s % 998244353)
    q -= 1

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, q = map(int, input().split())
    f = ['0'] + ['1' for i in range(n)]
    for _ in range(q):
        l, r, d = map(int, input().split())
        d = str(d)
        f[l:r+1] = list(d*(r-l+1))
        print(int(''.join(f)) % 998244353)


def main():
    t = 1
    while t > 0:
        solve()
        t -= 1


main()

Submission status: Memory Limit Exceeded

Solution code:
N, Q = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(Q)]

mod = 998244353

l = []
for i in range(1, 10):
    lt = []
    t = ''
    for j in range(20000):
        t += str(i)
        lt.append(t)
    l.append(lt)

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 = x>>off, x%mask
    y0, y1 = y>>off, y%mask
    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))