Replace Digits SOLUTION ACL CONTEST

Replace Digits SOLUTION

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 Li,Ri and a character Di (which is a digit). Then, you must replace all characters from the Li-th to the Ri-th (inclusive) with 

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

998,244,353.

Constraints

1

N

,

Q

200

,

000

1

L

i

R

i

N

1

D

i

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 

Copy

8 5

3 6 2

1 4 7

3 8 3

2 2 2

4 5 1

Sample Output 1 

Copy

11222211

77772211

77333333

72333333

72311333

Sample Input 2 

Copy

200000 1

123 456 7

Sample Output 2 

Copy

641437905

Don’t forget to take the modulo.

Related :

Leave a Comment

close
error: Content is protected !!