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: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase


class LazySegmentTree:
    def __init__(self, L):
        """initialize the lazy segment tree with data"""
        self.MOD = 998244353
        self.precompute = [0] * (L + 1)
        self.precompute[1] = 1
        for i in range(1, L + 1):
            self.precompute[i] = (self.precompute[i - 1] * 10 + 1) % self.MOD

        self._len = L
        self._size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * self._size)

        self.data = [1] * (self._size * 2)
        self.S = [1] * (self._size * 2)
        for i in range(self._size - 1, 0, -1):
            self.S[i] = self.S[i + i] + self.S[i + i + 1]
            self.data[i] = self._func(i + i, i + i + 1)
        
    
    def _func(self, a, b):
        return (self.data[a] * pow(10, self.S[b], self.MOD) + self.data[b]) % self.MOD

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._apply(2 * idx, q)
        self._apply(2 * idx + 1, q)

    def _apply(self, idx, tag):
        if tag == 0: return
        self._lazy[idx] = tag
        self.data[idx] = (tag * self.precompute[self.S[idx]]) % self.MOD

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            # if self._lazy[idx >> i] > 0:
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            if self._lazy[idx] == 0:
                self.data[idx] = self._func(2 * idx, 2 * idx + 1)
            idx >>= 1

    def update(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        # push first
        self._update(start)
        self._update(stop - 1)

        while start < stop:
            if start & 1:
                self._apply(start, value)
                start += 1
            if stop & 1:
                stop -= 1
                self._apply(stop, value)
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    # def query(self, start, stop):
    #     """func of data[start, stop)"""
    #     start += self._size
    #     stop += self._size

    #     # Apply all the lazily stored queries
    #     self._update(start)
    #     self._update(stop - 1)

    #     resL = [0, 0]
    #     resR = [0, 0]
    #     while start < stop:
    #         if start & 1:
    #             # resL = self._func(resL, self.data[start])
    #             resL[0] = (resL[0] * pow(10, self.S[start], self.MOD) + self.data[start]) % self.MOD
    #             resL[1] += self.S[start]
    #             start += 1
    #         if stop & 1:
    #             stop -= 1
    #             # resR = self._func(self.data[stop], resR)
    #             resR[0] = (self.data[stop] * pow(10, resR[1], self.MOD) + resR[0]) % self.MOD
    #             resR[1] += self.S[stop]
    #         start >>= 1
    #         stop >>= 1
    #     return (resL[0] * pow(10, resR[1], self.MOD) + resR[0]) % self.MOD

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)

def main():
    n, q = getints()
    st = LazySegmentTree(n)
    for _ in range(q):
        L, R, D = getints()
        st.update(L - 1, R, D)
        print(st.data[1])


# region fastio


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase


class LazySegmentTree:
    def __init__(self, L):
        """initialize the lazy segment tree with data"""
        self.MOD = 998244353
        self.precompute = [0] * (L + 1)
        self.precompute[1] = 1
        for i in range(1, L + 1):
            self.precompute[i] = (self.precompute[i - 1] * 10 + 1) % self.MOD

        self._len = L
        self._size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * self._size)

        self.data = [1] * (self._size * 2)
        self.S = [1] * (self._size * 2)
        for i in range(self._size - 1, 0, -1):
            self.S[i] = self.S[i + i] + self.S[i + i + 1]
            self.data[i] = self._func(i + i, i + i + 1)
        
    
    def _func(self, a, b):
        return (self.data[a] * pow(10, self.S[b], self.MOD) + self.data[b]) % self.MOD

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._apply(2 * idx, q)
        self._apply(2 * idx + 1, q)

    def _apply(self, idx, tag):
        if tag == 0: return
        self._lazy[idx] = tag
        self.data[idx] = (tag * self.precompute[self.S[idx]]) % self.MOD

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            if self._lazy[idx >> i] > 0:
                self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            if self._lazy[idx] == 0:
                self.data[idx] = self._func(2 * idx, 2 * idx + 1)
            idx >>= 1

    def update(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        # push first
        self._update(start)
        self._update(stop - 1)

        while start < stop:
            if start & 1:
                self._apply(start, value)
                start += 1
            if stop & 1:
                stop -= 1
                self._apply(stop, value)
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    # def query(self, start, stop):
    #     """func of data[start, stop)"""
    #     start += self._size
    #     stop += self._size

    #     # Apply all the lazily stored queries
    #     self._update(start)
    #     self._update(stop - 1)

    #     resL = [0, 0]
    #     resR = [0, 0]
    #     while start < stop:
    #         if start & 1:
    #             # resL = self._func(resL, self.data[start])
    #             resL[0] = (resL[0] * pow(10, self.S[start], self.MOD) + self.data[start]) % self.MOD
    #             resL[1] += self.S[start]
    #             start += 1
    #         if stop & 1:
    #             stop -= 1
    #             # resR = self._func(self.data[stop], resR)
    #             resR[0] = (self.data[stop] * pow(10, resR[1], self.MOD) + resR[0]) % self.MOD
    #             resR[1] += self.S[stop]
    #         start >>= 1
    #         stop >>= 1
    #     return (resL[0] * pow(10, resR[1], self.MOD) + resR[0]) % self.MOD

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)

def main():
    n, q = getints()
    st = LazySegmentTree(n)
    for _ in range(q):
        L, R, D = getints()
        st.update(L - 1, R, D)
        print(st.data[1])


# region fastio


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import os
import sys
from io import BytesIO, IOBase


class LazySegmentTree:
    def __init__(self, data, default=[0, 0]):
        """initialize the lazy segment tree with data"""
        self.MOD = 998244353
        self.precompute = [0] * (len(data) + 1)
        self.precompute[1] = 1
        for i in range(1, len(data) + 1):
            self.precompute[i] = (self.precompute[i - 1] * 10 + 1) % self.MOD
        
        self._default = default

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = self._func(self.data[i + i], self.data[i + i + 1])
        
    
    def _func(self, a, b):
        return [(a[0] * pow(10, b[1], self.MOD) + b[0]) % self.MOD, a[1] + b[1]]

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._apply(2 * idx, q)
        self._apply(2 * idx + 1, q)

    def _apply(self, idx, tag):
        if tag == 0: return
        self._lazy[idx] = tag
        self.data[idx][0] = tag * self.precompute[self.data[idx][1]] % self.MOD

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            if self._lazy[idx] == 0:
                self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            # else:
            #     self.data[idx][0] = self._lazy[idx] * self.precompute[self.data[idx][1]] % self.MOD
            idx >>= 1

    def update(self, start, stop, value):
        """lazily add value to [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._apply(start, value)
                start += 1
            if stop & 1:
                stop -= 1
                self._apply(stop, value)
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop - 1)

        resL = [0, 0]
        resR = [0, 0]
        while start < stop:
            if start & 1:
                resL = self._func(resL, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                resR = self._func(self.data[stop], resR)
            start >>= 1
            stop >>= 1
        return self._func(resL, resR)[0]

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)

def main():
    n, q = getints()
    data = [[1, 1] for _ in range(n)]
    st = LazySegmentTree(data)
    while q:
        L, R, D = getints()
        st.update(L - 1, R, D)
        # print(st)
        print(st.query(0, n))
        q -= 1


# region fastio


BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")
def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint1(): return list(map(lambda x: int(x) - 1, input().split()))


# endregion


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,Q = IL()
base = 10**6

class RUQ:
  def __init__(self, N, default = None):
    self.N0 = 2**(N-1).bit_length()
    self.data = [(-1, default)]*(2*self.N0)
    self.INF = (-1, default)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  def update(self, l, r, v):
    L = l + self.N0; R = r + self.N0
    while L < R:
      if R & 1:
        R -= 1
        self.data[R-1] = v
      if L & 1:
        self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1
  # a_iの現在の値を取得
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  # これを呼び出す
  def query(self, k):
    temp = self._query(k)[1]
    return temp//(base**2), (temp%(base**2))//base, temp%base
  
ST = RUQ(220000,1*base**2+1*base+N)

ichiga = [0]
for _ in range(N):
  ichiga.append((ichiga[-1]*10+1)%MOD)

ans = ichiga[-1]

for i in range(Q):
  l,r,d = IL()
  p = l
  while p <= r:
    x,f,t = ST.query(p)
    ans -= (ichiga[N-p+1]-ichiga[N-min(t,r)])*x
    ans %= MOD
    p = t+1  
  x,f,t = ST.query(l)
  ST.update(f,l,(i*3,x*base**2+f*base+l-1))
  x,f,t = ST.query(r)
  ST.update(r,t+1,(i*3+1,x*base**2+r*base+t))
  ST.update(l,r+1,(i*3+2,d*base**2+l*base+r))
  ans += (ichiga[N-l+1]-ichiga[N-r])*d
  ans %= MOD
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,Q = IL()
base = 10**6

class RUQ:
  def __init__(self, N, default = None):
    self.N0 = 2**(N-1).bit_length()
    self.data = [(-1, default)]*(2*self.N0)
    self.INF = (-1, default)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  def update(self, l, r, v):
    L = l + self.N0; R = r + self.N0
    while L < R:
      if R & 1:
        R -= 1
        self.data[R-1] = v
      if L & 1:
        self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1
  # a_iの現在の値を取得
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  # これを呼び出す
  def query(self, k):
      return self._query(k)[1]
  
ST = RUQ(220000,1*base**2+1*base+N)

ichiga = [0]
for _ in range(N):
  ichiga.append((ichiga[-1]*10+1)%MOD)

ans = ichiga[-1]

for i in range(Q):
  l,r,d = IL()
  p = l
  while p <= r:
    temp = ST.query(p)
    x,f,t = temp//(base**2), (temp%(base**2))//base, temp%base
    ans -= (ichiga[N-p+1]-ichiga[N-min(t,r)])*x
    ans %= MOD
    p = t+1  
  temp = ST.query(l)
  x,f,t = temp//(base**2), (temp%(base**2))//base, temp%base
  ST.update(f,l,(i*3,x*base**2+f*base+l-1))
  temp = ST.query(r)
  x,f,t = temp//(base**2), (temp%(base**2))//base, temp%base
  ST.update(r,t+1,(i*3+1,x*base**2+r*base+t))
  ST.update(l,r+1,(i*3+2,d*base**2+l*base+r))
  ans += (ichiga[N-l+1]-ichiga[N-r])*d
  ans %= MOD
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,Q = IL()

class RUQ:
  def __init__(self, N, default = None):
    self.N0 = 2**(N-1).bit_length()
    self.data = [(-1, default)]*(2*self.N0)
    self.INF = (-1, default)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  def update(self, l, r, v):
    L = l + self.N0; R = r + self.N0
    while L < R:
      if R & 1:
        R -= 1
        self.data[R-1] = v
      if L & 1:
        self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1
  # a_iの現在の値を取得
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  # これを呼び出す
  def query(self, k):
      return self._query(k)[1]
  
ST = RUQ(220000,(1,1,N))

ichiga = [0]
for _ in range(N):
  ichiga.append((ichiga[-1]*10+1)%MOD)

ans = ichiga[-1]

for i in range(Q):
  l,r,d = IL()
  p = l
  while p <= r:
    x,f,t = ST.query(p)
    ans -= (ichiga[N-p+1]-ichiga[N-min(t,r)])*x
    ans %= MOD
    p = t+1  
  x,f,t = ST.query(l)
  ST.update(f,l+1,(i*3,(x,f,l-1)))
  x,f,t = ST.query(r)
  ST.update(r,t,(i*3,(x,r,t)))
  ST.update(l,r+1,(i*3+1,(d,l,r)))
  ans += (ichiga[N-l+1]-ichiga[N-r])*d
  ans %= MOD
  print(ans)