# Replace Digits SOLUTION ACL CONTEST

Page Contents

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