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 a₁, a₂, …, a_n be the minimum integer d such that there exists a polynomial p of degree d for which p(x) = a_x 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 a₁, a₂, ..., a_n of size n, your task is to construct a sequence b₁, b₂, …, b_n+m of size n+m such that:

The first line of input contains two integers n and m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 8 · 10⁵).

The second line of input contains n integers a_i: the initial sequence (0 ≤ a_i < 998 244 353).

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