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 = map(int,input().split())

s = '1' * n

mod = 998244353

for _ in range(q):
    l,r,d = input().split()
    l,r = map(lambda x: x-1,map(int,[l,r]))
    s = s[:l] + d * (r-l+1) + s[r+1:]
    
    ans = 0
    for i in range(len(s) // 7):
        ans *= 10000000
        ans = (ans + int(s[i*7:i*7+7])) % mod
    rem = len(s) % 7
    if(rem):
        ans *= (10 ** rem)
        ans = (ans + int(s[-rem:])) % mod
    print(ans)

Submission status: Time Limit Exceeded

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

ans_l = [1] * n
ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

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

mod = 998244353
S = '1'*N
for l, r, d in LRD:
    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())
ls=[1]*(n)
N = 998244353
num = int('1'*n)
ans=[]
for _ in range(q):
    l,r,d= map(int, input().split())
    for i in range(l-1, r):
        num += (d-ls[i]) * (10**(n-i-1))
        ls[i]=d
    ans.append(num%N)
for i in ans:
    print(i)

Submission status: Time 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):
    t = ''
    for j in range(20000):
        t += str(i)
    l.append(t)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1]
    t = l[LRD[i][2] - 1]
    while len(t) < LRD[i][1] - LRD[i][0] + 1:
        t += t
    Sn += t[:LRD[i][1] - LRD[i][0] + 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
a=[]
for _ in range(Q):
    r,l,d=map(int,input().split())
    a.append([r,l,d])

S="1"*N
for q in a:
    S=S[:q[0]-1]+str(q[2])*(q[1]-q[0]+1)+S[q[1]:]
    print(int(S)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split(" "))
lrd = []
for i in range(q):
  tmp = input().split(" ")
  lrd.append([int(tmp[0]), int(tmp[1]), tmp[2]])
#lrd = [list(map(int, input().split(" "))) for i in range(q)]
mod = 998244353

ls = ['1']*n
for l,r,d in lrd:
  ls = ls[:l-1] + [d] * (r-l+1) + ls[r:]
  #print(ls)
  txt = ''.join(ls)
  print(int(txt)%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

def get_ints():
    return map(int, input().strip().split())


def main():
    n, q = get_ints()
    s = "1" * n
    s = int(s)
    mod = 998244353

    for i in range(q):
        l, r, d = map(int, input().split())
        ll = s // (10 ** (n-l+1)) * (10 ** (n-l+1))
        rr = s % (10 ** (n-r))
        dd = int(str(d) * (r-l+1)) * (10 ** (n-r))
        s = ll + dd + rr
        print(s % mod)


if __name__ == "__main__":
    main()

Submission status: Time 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):
    t = ''
    for j in range(20000):
        t += str(i)
    l.append(t)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1]
    t = l[LRD[i][2] - 1]
    while len(t) < LRD[i][1] - LRD[i][0] + 1:
        t += t
    Sn += t[:LRD[i][1] - LRD[i][0] + 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(int(S) % mod)

Submission status: Time Limit Exceeded

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

MOD = 998244353
S = ['1'] * N
for L,R,D in LRD:
    S[L-1:R] = [str(D)] * (R-L+1)
    ans = int(''.join(S))
    print(ans%MOD)

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 = (int(x) for x in input().split())

lrd = []
for i in range(q):
  lrd.append([int(x) for x in input().split()])

s = 0
for a in range(n):
  s += 10**a


for j in lrd:
  for a in range(j[1]-j[0]+1):
    s -= ((s // (10 ** (n-j[1]+a))) % 10) * 10 ** (n-j[1]+a)
    s += j[2] * 10 ** (n-j[1]+a)
  print(s % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N, Q = i_map()
    S = "1"*N

    for i in range(Q):
        l,r,q = i_map()
        q = str(q)
        
        S = S[:l-1] + S[l-1:].replace(S[l-1:r],q*(r-l+1),1)
        print(int(S) % 998244353)



 

if __name__=="__main__":
    main()

Submission status: Time 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(2000):
        t += str(i)
        lt.append(t)
    l.append(lt)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1]
    t = l[LRD[i][2] - 1][2000 - 1]
    while len(t) < LRD[i][1] - LRD[i][0] + 1:
        t += t
    Sn += t[:LRD[i][1] - LRD[i][0] + 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(int(S) % mod)

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(i) for i in input().split()]
S = '1'*N

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

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:]
  if n>9:
    print(int(s)%998244353)
  else:
    print(int(s))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
k = ["1"]*N
#print(k[1])
for i in range(Q):
    a, b, c= map(str, input().split())
    for n in range(int(a)-1,int(b)):
        k[n] = c
    k_a =int( "".join(k))
    k_a %= 998244353
    print(str(k_a))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
MOD=998244353
s=0
dic='1'*N
P=[]
for i in range(N):
  s+=pow(10,i,MOD)
  P.append(pow(10,i,MOD))
for q in range(Q):
  l,r,d=map(int,input().split())
  _=(int(str(d)*(r-l+1))-int(dic[l-1:r]))%MOD
  dic=dic[:l-1]+str(d)*(r-l+1)+dic[r:]
  s+=(_*P[N-r])%MOD
  print(s%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

def get_ints():
    return map(int, input().strip().split())


def main():
    n, q = get_ints()
    s = "1" * n
    s = int(s)
    mod = 998244353

    for i in range(q):
        l, r, d = map(int, input().split())
        ll = s // (10 ** (n-l+1)) * (10 ** (n-l+1))
        rr = s % (10 ** (n-r))
        dd = int(str(d) * (r-l+1)) * (10 ** (n-r))
        s = ll + dd + rr
        print(int(s) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

outs = []
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:]
  outs.append(int(s) % 998244353)

for out in outs:
  print(out)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
string = ["1"] * n

for i in range(q):
    l,r,d = map(int, input().split())
    string[l-1:r]  = str(d) * (r-l+1)
    joined = ''.join(string)
    print(int(joined) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import atexit
import io
import sys

_INPUT_LINES = sys.stdin.read().splitlines()
raw_input = iter(_INPUT_LINES).next
_OUTPUT_BUFFER = io.BytesIO()
sys.stdout = _OUTPUT_BUFFER


@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

n,m = map(int,raw_input().split())
s = "1"*n
for i in range(m):
  l,r,k = map(int,raw_input().split())
  s =  s[:l-1]+str(k)*(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 _ in range(q):
    l, r, d = map(int, input().split())
    tmp = str(d) * (r - l + 1)
    s = str(int(s[:l - 1] + tmp + s[r:]) % 998244353)
    print(s)

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
n,q=map(int,input().split())
lrd=[list(map(int,input().split())) for _ in range(q)]
s=0
ss=[]
tmp=1
for i in range(n):
  ss.append(tmp)
  s+=tmp
  s%=mod
  tmp*=10
  tmp%=mod
ss.reverse()
#print(ss,s)
for l,r,d in lrd:
  for i in range(l-1,r):
    s-=ss[i]
    ss[i]=d*pow(10,n-i-1,mod)
    s+=ss[i]
    s%=mod
  print(s)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
mod=998244353
s=['1' for _ in range(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(pow(int(''.join(s)),1,mod))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# # input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,q = inpm()
LRD = inplt(q)

s = list('1'*n)
for l,r,d in LRD:
    s = s[:l-1] + list(str(d)*(r-l+1)) + s[r:]
    print(int(''.join(s)) % mod)

Submission status: Time Limit Exceeded

Solution code:
class lazySegTree:
  #遅延評価セグメント木
  def __init__(s, op, e, mapping, composition, id, v):
    if type(v) is int: v = [e()] * v
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.lz = [id()] * s.size
    s.e = e
    s.op = op
    s.mapping = mapping
    s.composition = composition
    s.id = id
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    return s.d[p]
 
  # 区間演算
  def prod(s, l, r):
    if l == r: return s.e()
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push(r >> i)
    sml, smr = s.e(), s.e()
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # 1点写像
  def apply(s, p, f):
    p += s.size
    for i in range(s.log, 0, -1): s.push(p >> i)
    s.d[p] = s.mapping(f, s.d[p])
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 区間写像
  def apply(s, l, r, f):
    if l == r: return
    l += s.size
    r += s.size
    for i in range(s.log, 0, -1):
      if (((l >> i) << i) != l): s.push(l >> i)
      if (((r >> i) << i) != r): s.push((r - 1) >> i)
    l2, r2 = l, r
    while l < r:
      if l & 1: 
        sml = s.all_apply(l, f)
        l += 1
      if r & 1:
        r -= 1
        smr = s.all_apply(r, f)
      l >>= 1
      r >>= 1
    l, r = l2, r2
    for i in range(1, s.log + 1):
      if (((l >> i) << i) != l): s.update(l >> i)
      if (((r >> i) << i) != r): s.update((r - 1) >> i)
   
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    for i in range(s.log, 0, -1): s.push(l >> i)
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          s.push(l)
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    for i in range(s.log, 0, -1): s.push((r - 1) >> i)
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          s.push(r)
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def all_apply(s, k, f):
    s.d[k] = s.mapping(f, s.d[k])
    if k < s.size: s.lz[k] = s.composition(f, s.lz[k])
  def push(s, k):
    s.all_apply(2 * k, s.lz[k])
    s.all_apply(2 * k + 1, s.lz[k])
    s.lz[k] = s.id()
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x

# return a・e = a となる e
def e():
  return 0

# return a・b
def op(a, b):
  a0, a1 = a >> 18, a & ((1 << 18) - 1)
  b0, b1 = b >> 18, b & ((1 << 18) - 1)
  return (((a0 * pow(10, b1) + b0) % MOD) << 18) + a1 + b1

# return f(a)
def mapping(f, a):
  if f == 0: return a
  a0, a1 = a >> 18, a & ((1 << 18) - 1)
  return (D[f][a1] << 18) + a1

# return f・g
# gを写像した後にfを写像した結果
def composition(f, g):
  if f == 0: return g
  return f

# return f(id) = id となる id
def id():
  return 0

N, Q = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(Q)]
MOD = 998244353

D = [[0]]
for i in range(1, 10):
  D.append([0])
  for j in range(N):
    D[i].append((D[i][-1] * 10 + i) % MOD)

a = [(1 << 18) + 1 for _ in range(N)]
seg = lazySegTree(op, e, mapping, composition, id, a)
for l, r, d in LRD:
  seg.apply(l - 1, r, d)
  ans = seg.all_prod()
  print(ans >> 18)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,q = inpm()
LRD = inplt(q)

s = list('1'*n)
for l,r,d in LRD:
    s = s[:l-1] + list(str(d)*(r-l+1)) + s[r:]
    print(int(''.join(s)) % mod)

Submission status: Time Limit Exceeded

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

S = "1" * N
mod = 998244353

L, R, D = [0]*Q, [0]*Q, [0]*Q
for i in range(Q):
    l, r, d = map(int, input().split())
    l, r = l-1, r-1
    L[i], R[i], D[i] = l, r, d

for i, d in enumerate(D):
    l, r = L[i], R[i]
    head = S[:l]
    tail = S[r+1:]
    S = head + str(d) * (r - l + 1) + tail
    print(int(S) % mod)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
from collections import deque, defaultdict, Counter
import heapq

def main():
    N, Q = MI()
    S = '1' * N
    mod = 998244353
    ans = int(S) % mod
    for i in range(Q):
        l, r, d = MI()
        l -= 1
        r -= 1
        ans += (((int(str(d) * (r - l + 1))) % mod - (int(S[l:r + 1])) % mod) * (10 ** (N - r - 1)) % mod) % mod
        ans %= mod
        S = S[0:l] + str(d) * (r - l + 1) + S[r + 1:]
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
t = '1' * n
mod = 998244353

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

Submission status: Time Limit Exceeded

Solution code:
def LI():
    return list(map(int, input().split()))


mod = 998244353

N, Q = LI()
S = "1"*N
for _ in range(Q):
    L, R, D = LI()
    D = str(D)
    S = S[:L-1]+D*(R-L+1)+S[R:N]
    print(int(S) % mod)

Submission status: Time Limit Exceeded

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abl/abl_e
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

P = 998_244_353

def f(n, m=1):
    return ((10 ** n - 1) // 9 * m) % P

def main():
    N, Q = i2nn()
    S = '1' * N
    A = f(N)
    for _ in range(Q):
        L, R, D = i2nn()
        T = S[L-1:R]
        E = 10**(N-R) % P
        B = ((int(T) % P) * E) % P
        C = (f(R - L + 1, D) * E) % P
        A = (A - B + C) % P
        print(A)
        S = f'{S[:L-1]}{str(D)*(R-L+1)}{S[R:]}'
    return

main()

Submission status: Time Limit Exceeded

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


class LazySegmentTree:
    def __init__(self, n, unitX, unitA, X_f, A_f, XA_map):
        self.n = n
        self.unitX = unitX
        self.unitA = unitA
        self.X_f = X_f  # (X, X) -> X
        self.A_f = A_f  # (A, A) -> A
        self.XA_map = XA_map  # (X, A) -> X
        self.X = [unitX] * (n + n)
        self.A = [unitA] * (n + n)

    def __getitem__(self, i):
        i += self.n
        self._propagate_above(i)
        return self.X[i]

    def __setitem__(self, i, x):
        i += self.n
        self._propagate_above(i)
        self.X[i] = x
        self._calc_above(i)

    def build(self, array):
        for i, val in enumerate(array, self.n):
            self.X[i] = val
        for i in range(self.n - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _calc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _propagate_above(self, i):
        k = i >> 1
        H = k.bit_length() - 1
        for h in range(H, -1, -1):
            i = k >> h
            if self.A[i] == self.unitA:
                continue
            self.X[i << 1] = self.XA_map(self.X[i << 1], self.A[i])
            self.X[i << 1 | 1] = self.XA_map(self.X[i << 1 | 1], self.A[i])
            self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i])
            self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
            self.A[i] = self.unitA

    def fold(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        xl = self.unitX
        xr = self.unitX
        while l < r:
            if l & 1:
                xl = self.X_f(xl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                xr = self.X_f(self.X[r], xr)
            l >>= 1
            r >>= 1
        return self.X_f(xl, xr)

    def apply(self, i, a):
        i += self.n
        self._propagate_above(i)
        self.X[i] = self.XA_map(self.X[i], a)
        self.A[i] = self.A_f(self.A[i], a)
        self._calc_above(i)

    def apply_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        while l < r:
            if l & 1:
                self.X[l] = self.XA_map(self.X[l], a)
                self.A[l] = self.A_f(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.X[r] = self.XA_map(self.X[r], a)
                self.A[r] = self.A_f(self.A[r], a)
            l >>= 1
            r >>= 1
        self._calc_above(l0)
        self._calc_above(r0)

      
n, q = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(q)]
MOD = 998244353


unitX = (0, 0, 0)
pow_ = [1] * (n + 1)
for i in range(n):
    pow_[i + 1] = (pow_[i] * 10) % MOD

digit = [[0] * (n + 1) for i in range(10)]
for i in range(n):
    for val in range(10):
        digit[val][i + 1] = (digit[val][i] + pow_[i] * val) % MOD

def X_f(x1, x2):
    return (x1[0] * pow_[abs(x1[1] - x2[1])] + x2[0]) % MOD, x2[1], x1[2] + x2[2]

unitA = 100
A_f = lambda a1, a2: a1 if a2 == unitA else a2
def XA_map(x, a):
    if a != unitA: return digit[a][x[2]] % MOD, x[1], x[2]



lst = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map) 
lst.build([(1, n - i - 1, 1) for i in range(n)])

# print([lst.fold(i, i + 1) for i in range(n)])
# print(lst.fold(0, n))
ans = []

for l, r, d in queries:
    l -= 1
    lst.apply_range(l, r, d)
    # print([lst.fold(i, i + 1) for i in range(n)])
    ans.append(lst.fold(0, n)[0])
    
print(*ans, sep="\n")

Submission status: Time 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(2000):
        t += str(i)
        lt.append(t)
    l.append(lt)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1] + l[LRD[i][2] - 1][LRD[i][1] - LRD[i][0]]
    sho = (LRD[i][1] - LRD[i][0] + 1) // 2000
    yo = (LRD[i][1] - LRD[i][0] + 1) % 2000
    for i in range(sho):
        if i == sho - 1:
            Sn += l[LRD[i][2] - 1][yo - 1]
        else:
            Sn += l[LRD[i][2] - 1][2000 - 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(S)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
MOD=998244353
s=0
dic=[1]*(N+1)
P=[]
for i in range(N):
  s+=pow(10,i,MOD)
  P.append(pow(10,i,MOD))
for q in range(Q):
  l,r,d=map(int,input().split())
  _=0
  for i in range(l,r+1):
    _*=10
    _+=d-dic[i]
    dic[i]=d
    _%=MOD
  s+=(_*P[N-r])%MOD
  print(s%MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = [int(x) for x in input().split()]
    MOD = 998244353
    S = ['1'] * N

    for _ in range(Q):
        l, r, d = [int(x) for x in input().split()]
        x = [str(d)] * (r - l + 1)
        new_str = S[:l-1]
        new_str.extend(x)
        new_str.extend(S[r:])
        S = new_str

        result = int(''.join(S)) % MOD
        print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

N, Q = list(map(int, sys.stdin.readline().strip().split(" ")))

S = "1" * N
x = 998244353
  

for q in range(Q):
    L, R, D = sys.stdin.readline().strip().split(" ")
    L, R = int(L) - 1, int(R) - 1

    S = S[:L] + D * (R - L + 1) + S[R + 1:]
    print(int(S) % x)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
N,Q=map(int, input().split())
S='1'*N
for i in range(Q):
    l,r,d = input().split()
    l = int(l)
    r = int(r)
    S = S[:l-1]+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
for _ in range(q):
    l, r, d = map(int,input().split())
    tmp = str(d) * (r - l + 1)
    s = s[:l-1] + tmp + s[r:]
    ss = int(s)
    ss %= 998244353
    print(ss)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = list(map(int, input().split(" ")))
    s = "1" * n

    #str_list = []
    ans_list = []
    for _ in range(q):
        l, r, d = list(map(int, input().split(" ")))
        s = s[:l-1] + str(d)*(r-l+1) + s[r:]
        #str_list.append([s[:l-1], str(d)*(r-l+1), s[r:]])
        print(int(s)%998244353)

    #print(*str_list)

if __name__=="__main__":
    main()

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())
  L = r-l+1
  s = s[:l-1]+(str(d)*L)+s[r:]
  
  print(int(s)%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
try:sys.stdin,sys.stdout=open('in.txt','r'),open('out.txt','w')
except:pass
ii1=lambda:int(sys.stdin.readline().strip()) # for interger
is1=lambda:sys.stdin.readline().strip() # for str
iia=lambda:list(map(int,sys.stdin.readline().strip().split())) # for List[int]
isa=lambda:sys.stdin.readline().strip().split() # for List[str]
mod=int(1e9 + 7);from collections import *;from math import *

###################### Start Here ######################
mod = 998244353
n, q = iia()
arr = [1]*n
for i in range(q):
    a,b,val=iia()
    a-=1
    ans=''
    for i in range(n):
        if a<=i<b:
            ans+=str(val)
            arr[i]=val
        else:
            ans+=str(arr[i])
    print(int(ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
start_num,N = input().split()
start_num =[1]*int(start_num)

for i in range(int(N)):
    input_val = list(map(int, input().split()))
    standard_num = input_val[1]-input_val[0]+1
    
    for j in range(standard_num):
        start_num[input_val[0]-1+j]=input_val[2]

    last_num =""
    for k in range(len(start_num)):
        last_num += str(start_num[k])
    if i == int(N)-1:
        print(int(last_num)%998244353)
    else:
        print(last_num)

Submission status: Time Limit Exceeded

Solution code:
##import sys
##sys.setrecursionlimit(10**6)
##
##N = 10**5+1
##g = [[] for i in range(N)]
##
##vis = [False for i in range(N)]
##
##good = [False for i in range(N)] 
##  
##def ADD_EDGE(u, v): 
##    g[u].append(v)
##    
##def dfs1(v): 
##    good[v] = True
##    for to in g[v]: 
##        if not good[to]: 
##            dfs1(to)
##            
##def dfs2(v):
##    global cnt 
##    vis[v] = True
##    cnt += 1
##    for to in g[v]: 
##        if not vis[to] and not good[to]: 
##            dfs2(to)
##            
##def Minimum_Edges():
##    global vis, cnt
##    dfs1(x)
##    
##    val = [] 
##  
##    for i in range(0, n):
##        if not good[i]: 
##            cnt = 0
##            vis = [False for i in range(N)]
##            
##            dfs2(i) 
##            val.append((cnt, i))
##            
##    val.sort(reverse = True)
##    
##    ans = 0
##    for it in val:  
##        if not good[it[1]]:  
##            ans += 1
##            dfs1(it[1]) 
##  
##    return ans
##
##
##
##n, m = map(int, input().split())
##
##for _ in range(m):
##    a, b = map(int, input().split())
##    ADD_EDGE(a, b)
##    ADD_EDGE(b, a)
##
##x = m
##
##print(Minimum_Edges())

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:
N, Q = [int(x) for x in input().split()]
MOD = 998244353
S = ['1'] * N

for _ in range(Q):
    l, r, d = [int(x) for x in input().split()]
    x = [str(d)] * (r - l + 1)
    new_str = S[:l-1]
    new_str.extend(x)
    new_str.extend(S[r:])
    S = new_str

    result = int(''.join(S)) % MOD
    print(result)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
mod=998244353
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)%mod)

Submission status: Time Limit Exceeded

Solution code:

def main():
    N, Q = map(int, input().split())
    S = '1'*N
    ans = []

    for q in range(Q):
        L, R, D = map(int, input().split())
        S = S[:L-1] + str(D)*(R-L+1) + S[R:]
        ans.append(int(S) % 998244353)
    
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()