Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 500 points
Problem Statement
You have a string S of length N.
Initially, all characters in S are 1
s.
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.
配点 : 500 点
問題文
長さ N の文字列 S があります。
最初は S のすべての文字が 1
です。
クエリを Q 回処理します。 i 番目のクエリでは、整数 L_i, R_i と文字 (数字) D_i が与えられます。 L_i 番目から R_i 番目までの全ての文字を D_i に書き換えてください。
各クエリの後、S を十進法で書かれた整数とみなし、その値を 998,244,353 でわった余りを出力してください。
制約
- 1 \leq N, Q \leq 200,000
- 1 \leq L_i \leq R_i \leq N
- 1 \leq D_i \leq 9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q L_1 R_1 D_1 : L_Q R_Q D_Q
出力
Q 行出力せよ。 i 行目には i 番目のクエリの後の S の値を modulo 998,244,353 で出力せよ。
入力例 1
8 5 3 6 2 1 4 7 3 8 3 2 2 2 4 5 1
出力例 1
11222211 77772211 77333333 72333333 72311333
入力例 2
200000 1 123 456 7
出力例 2
641437905
あまりをとるのを忘れないでください。