ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Petrozavodsk Summer 2018. t.me/umnik_team Contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Continue the Sequence

Time limit: 4.0 second
Memory limit: 128 MB
For sure you have seen puzzles like “Given the sequence, find its next element”. They seem logical in your childhood, but later you begin to understand that you can write any number and justify it with some tricky construction.
In this problem you have to continue the sequence “in the easiest way”. Still not strict enough? Let us give a formal definition.
Let the hardness of the sequence a1, a2, …, an be the minimum integer d such that there exists a polynomial p of degree d for which p(x) = ax mod 998 244 353 for all x from 1 to n. For this problem, consider the polynomial p(x) = 0 to have degree −1.
Given a sequence a1, a2, ..., an of size n, your task is to construct a sequence b1, b2, …, bn+m of size n+m such that:
  • 0 ≤ bi < 998 244 353 for all i from 1 to n+m,
  • ai = bi for all i from 1 to n,
  • The hardness of the sequence b is as small as possible.

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 8 · 105).
The second line of input contains n integers ai: the initial sequence (0 ≤ ai < 998 244 353).

Output

Print m integers bn+1, bn+2, …, bn+m separated by spaces.

Samples

inputoutput
5 10
1 4 9 16 25
36 49 64 81 100 121 144 169 196 225 
3 3
0 0 0
0 0 0 
5 10
1 2 4 8 16
31 57 99 163 256 386 562 794 1093 1471 
3 1
2 1 0
998244352 
Problem Author: Alexey Danilyuk, Oleg Merkurev
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest
To submit the solution for this problem go to the Problem set: 2125. Continue the Sequence