ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

2125. Продолжи последовательность

Ограничение времени: 4.0 секунды
Ограничение памяти: 128 МБ
Наверняка вы не раз видели головоломки вида «Дана последовательность, найдите следующее число». В детстве они кажутся логичными, но потом приходит понимание, что можно написать любое число, а затем объяснить это какой-нибудь хитрой конструкцией.
Вам мы предлагаем продолжить последовательность «наиболее простым способом». Всё ещё недостаточно строго? Дадим точное определение.
Сложностью последовательности a1, a2, …, an называется минимальное такое d, что существует многочлен p степени d такой, что p(x) = ax mod 998 244 353 для всех x от 1 до n. В рамках этой задачи считайте, что степень многочлена p(x) = 0 равна −1.
Вам дана последовательность a1, a2, ..., an длины n, вам нужно построить последовательность b1, b2, …, bn+m длины n+m такую, что:
  • 0 ≤ bi < 998 244 353 для всех i от 1 до n+m
  • ai = bi для всех i от 1 до n
  • Сложность последовательности b как можно меньше.

Исходные данные

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

Результат

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

Примеры

исходные данныерезультат
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 
Автор задачи: Алексей Данилюк, Олег Меркурьев
Источник задачи: Петрозаводск лето 2018. t.me/umnik_team Contest