Когда говорят о сумчатых млекопитающих, первым делом в голову приходят кенгуру, затем уже опоссумы, бандикуты и другие. На днях Вадим открыл новый вид сумчатых и назвал его «Префоссумы». Это очень удивительные существа, их размер сопоставим с молодыми кротами, жёлто-рыжая расцветка с белыми пятнами, длинный и пушистый хвост, но больше всего поражают их математические способности.

Если оставить префоссуму массив a из N чисел, то ровно за один день небольшой зверёк превратит его в массив префиксных сумм p исходного массива a. Это означает, что для любой позиции под номером i будет выполняться p_i = ∑ⁱ_j=1 a_j. Если не забрать у префоссума полученный массив, то он продолжит свои действия, но уже с новым массивом.

«Мир должен знать про это животное»,  — подумал Вадим и отправился писать письмо в IUBS, оставив у одного префоссума интересный массив v. Однако процесс оказался времязатратным, это всё заняло у Вадима Q дней, и он только сейчас вспомнил про оставленный массив. К сожалению, дела ещё не закончены, а текущий массив внести в письмо просто необходимо. Помогите Вадиму найти значения этого массива.

В первой строке даны два целых числа N и Q — количество чисел в исходном интересном массиве и количество дней, в течение которых этот массив был у префоссума (2 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁷).

Во второй строке даны N целых чисел v_i — значения исходного массива (1 ≤ v_i ≤ 10⁸).

Выведите N целых чисел — значения массива после Q дней пребывания с префоссумом по модулю 998 244 353.

В первый день префоссум преобразит исходный массив в массив [1, 3, 6].