C - Repunits Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

正整数 n に対して R_n を「1 を n 個並べてできる文字列を 10 進表記された整数と解釈したもの」として定義します。例えば R_3 = 111 です。

正整数列 A = (A_1, A_2, \dots, A_N) が与えられます。
k = 1, 2, \dots, N について \mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353 を計算してください。ここで \mathrm{LCM} は最小公倍数を計算する関数とします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 2 \times 10^5
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

N 行出力せよ。k 行目には \mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353 を出力せよ。

入力例 1

3
2 4 6

出力例 1

11
1111
11222211

k=1 について、\mathrm{LCM}(11) \bmod 998244353 = 11 です。
k=2 について、\mathrm{LCM}(11,1111) \bmod 998244353= 1111 です。
k=3 について、\mathrm{LCM}(11,1111,111111) \bmod 998244353= 11222211 です。

入力例 2

1
200000

出力例 2

202819780

入力例 3

10
47718 21994 98917 104184 160670 190107 125377 29127 7017 177076

出力例 3

429620650
844699313
355160870
608402385
858856681
605347397
566966598
429324494
370941155
567238109

Score : 900 points

Problem Statement

For a positive integer n, define R_n as "the integer obtained by interpreting a string of n consecutive 1s as a decimal number". For example, R_3 = 111.

You are given a positive integer sequence A = (A_1, A_2, \dots, A_N).
For k = 1, 2, \dots, N, calculate \mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353. Here, \mathrm{LCM} is the function that calculates the least common multiple.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 2 \times 10^5
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Output N lines. The k-th line should contain \mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_k}) \bmod 998244353.

Sample Input 1

3
2 4 6

Sample Output 1

11
1111
11222211

For k=1, \mathrm{LCM}(11) \bmod 998244353 = 11.
For k=2, \mathrm{LCM}(11,1111) \bmod 998244353= 1111.
For k=3, \mathrm{LCM}(11,1111,111111) \bmod 998244353= 11222211.

Sample Input 2

1
200000

Sample Output 2

202819780

Sample Input 3

10
47718 21994 98917 104184 160670 190107 125377 29127 7017 177076

Sample Output 3

429620650
844699313
355160870
608402385
858856681
605347397
566966598
429324494
370941155
567238109