Наверняка вы не раз видели головоломки вида «Дана последовательность, найдите следующее число». В детстве они кажутся логичными, но потом приходит понимание, что можно написать любое число, а затем объяснить это какой-нибудь хитрой конструкцией.

Вам мы предлагаем продолжить последовательность «наиболее простым способом». Всё ещё недостаточно строго? Дадим точное определение.

Сложностью последовательности a₁, a₂, …, a_n называется минимальное такое d, что существует многочлен p степени d такой, что p(x) = a_x mod 998 244 353 для всех x от 1 до n. В рамках этой задачи считайте, что степень многочлена p(x) = 0 равна −1.

Вам дана последовательность a₁, a₂, ..., a_n длины n, вам нужно построить последовательность b₁, b₂, …, b_n+m длины n+m такую, что:

В первой строке записано два целых числа n и m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 8 · 10⁵).

Во второй строке записаны n целых чисел a_i — исходная последовательность (0 ≤ a_i < 998 244 353).

Выведите m чисел b_n+1, b_n+2, …, b_n+m. Разделяйте числа пробелами.