{"raw_statement":[{"iden":"statement","content":"During your participation in this competition, Shinyruo is preparing to order KFC for the offline competition next week.\n\nThere are $n$ kinds of foods in KFC, and he plans to order $a_i$ number of the $i$-th food for every $i in [ 1, n ]$. Due to shortage of manpower, the total number of all kinds of foods is no larger than $10^5$.\n\nAfter the competition, he will hand all the KFC out to $k$ teams. Each team can get different kinds of foods but for each kind it can get one at most.\n\nNow Shinyruo wants to know the number of ways to hand the desserts out. As he doesn't know the number of participating teams, you need to calculate the answers for $k = 1, 2, \\\\\\\\cdots, m$.\n\nAs the answer can be large, print it modulo $998244353$.\n\nThe first line contains two integers $n, m$. ($1 <= m, n <= 5 dot.op 10^4$)\n\nThe second line contains $n$ integers $a_1, \\\\\\\\cdots, a_n$. ($0 <= a_i <= 10^5, \" \"sum_{i = 1}^n a_i <= 10^5$)\n\n$m$ lines each contains one integer. The $i$-th integer indicates the answer of $k = i$ modulo $998244353$.\n\n"},{"iden":"input","content":"The first line contains two integers $n, m$. ($1 <= m, n <= 5 dot.op 10^4$)The second line contains $n$ integers $a_1, \\\\\\\\cdots, a_n$. ($0 <= a_i <= 10^5, \" \"sum_{i = 1}^n a_i <= 10^5$)"},{"iden":"output","content":"$m$ lines each contains one integer. The $i$-th integer indicates the answer of $k = i$ modulo $998244353$."}],"translated_statement":[{"iden":"statement","content":"Карам учится в очень крутой школе. В конце каждого учебного года все ученики, даже самые одарённые и талантливые, подвергаются сдаче зачёта. В одной из таких зачетных работ по информатике Караму предстояло решить одну интересную задачу.\n\nЗадача состояла в следующем: на прямой отмечено $m$ точек, пронумерованных от $1$ до $m$. Также было дано $n$ отрезков, которые были пронумерованы от $1$ до $n$. Отрезок под номером $i$ мог покрыть точки с номерами от $l_i$ до $r_i$ включительно, и за такое покрытие взималась определенная стоимость $c_i$. Задача заключалась в том, чтобы покрыть все $m$ данных точек, стараясь при этом минимизировать затраты.\n\nКонечно же, Карам успешно справился с этой задачей и получил высокую оценку. Однако, он начал задумываться, что произойдет, если покрыть не все $m$ точек прямой, а оставить непокрытой ровно одну любую точку. Это стало для него интересным вызовом. Справитесь ли вы с этой задачей? \n\nПервая строка входных данных содержит два числа $n$ и $m$ $(1 lt.eq n, m lt.eq 300 \" \"000)$ — количество отрезков и количество точек на прямой соответственно.\n\nВ следующих $n$ строках описываются отрезки. Каждая строка содержит три целых числа $l_i$, $r_i$, $c_i$ $(1 lt.eq l_i lt.eq r_i lt.eq m, \" \"1 lt.eq c_i lt.eq 10^9)$ — границы отрезка и его стоимость cоответственно.\n\nВыведите стоимость минимального покрытия $m -1$ точки прямой или $-1$, если это невозможно. \n\nТесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.\n\nДавайте разберем первый пример.\n\nМожно оставить непокрытой первую точку, используя третий и четвертый отрезок, тогда стоимость покрытия будет равна $c_3 + c_4 = 4 + 2 = 6$.\n\nВторую точку можно оставить непокрытой, используя первый и четвертый отрезок, тогда стоимость покрытия будет равна $c_1 + c_4 = 3 + 2 = 5$.\n\nВсе точки, кроме третьей, можно покрыть, используя первый и третий отрезки, либо используя только второй отрезок. Стоимости таких покрытий будут равны $c_1 + c_3 = 7$ и $c_2 = 8$ соответственно.\n\nПолучается, что самым дешевым способом покрыть все точки, кроме одной, будет стоить $c_1 + c_4 = 5$.\n\nВо втором примере несложно заменить, что невозможно покрыть прямую так, чтобы непокрытой осталась ровно одна точка.\n\n"},{"iden":"входные данные","content":"Первая строка входных данных содержит два числа $n$ и $m$ $(1 lt.eq n, m lt.eq 300 \" \"000)$ — количество отрезков и количество точек на прямой соответственно.В следующих $n$ строках описываются отрезки. Каждая строка содержит три целых числа $l_i$, $r_i$, $c_i$ $(1 lt.eq l_i lt.eq r_i lt.eq m, \" \"1 lt.eq c_i lt.eq 10^9)$ — границы отрезка и его стоимость cоответственно."},{"iden":"выходные данные","content":"Выведите стоимость минимального покрытия $m -1$ точки прямой или $-1$, если это невозможно. "},{"iden":"система оценки","content":"Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.  *Группа**Баллы**Дополнительные ограничения**Необх. группы**Комментарий*00––Тесты из условия.111$1 lt.eq m lt.eq 2$–На прямой отмечено всего две точки.214$1 lt.eq n, m lt.eq 15$0321$1 lt.eq n, m lt.eq 1000$0, 2421$1 lt.eq n, m lt.eq 300 \" \"000$–Оптимально оставить непокрытой первую точку. Гарантируется, что ответ есть.533$1 lt.eq n, m lt.eq 300 \" \"000$0-4 "},{"iden":"примеры","content":"Входные данные4 3\n1 1 3\n1 2 8\n2 2 4\n3 3 2\nВыходные данные5\nВходные данные3 10\n1 5 13\n3 10 23\n5 7 11\nВыходные данные-1\n"},{"iden":"примечание","content":"Давайте разберем первый пример.  #cf_span(class=[tex-font-size-small], body=[Иллюстрация к первому примеру.]) Можно оставить непокрытой первую точку, используя третий и четвертый отрезок, тогда стоимость покрытия будет равна $c_3 + c_4 = 4 + 2 = 6$.  #cf_span(class=[tex-font-size-small], body=[Иллюстрация к первому способу.]) Вторую точку можно оставить непокрытой, используя первый и четвертый отрезок, тогда стоимость покрытия будет равна $c_1 + c_4 = 3 + 2 = 5$.  #cf_span(class=[tex-font-size-small], body=[Иллюстрация к второму способу.]) Все точки, кроме третьей, можно покрыть, используя первый и третий отрезки, либо используя только второй отрезок. Стоимости таких покрытий будут равны $c_1 + c_3 = 7$ и $c_2 = 8$ соответственно.  #cf_span(class=[tex-font-size-small], body=[Иллюстрация к третьему способу.])   #cf_span(class=[tex-font-size-small], body=[Иллюстрация к четвертому способу.]) Получается, что самым дешевым способом покрыть все точки, кроме одной, будет стоить $c_1 + c_4 = 5$.Во втором примере несложно заменить, что невозможно покрыть прямую так, чтобы непокрытой осталась ровно одна точка."}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of strings $ s $ and $ t $.  \nLet $ s, t \\in \\{a, b\\}^n $ be the two input strings.  \n\nLet $ D = \\{ i \\in \\{1, \\dots, n\\} \\mid s_i \\ne t_i \\} $ be the set of positions where $ s $ and $ t $ differ.  \n\nDefine:  \n- $ d_{ab} = |\\{ i \\in D \\mid s_i = a, t_i = b \\}| $  \n- $ d_{ba} = |\\{ i \\in D \\mid s_i = b, t_i = a \\}| $  \n\n**Constraints**  \n1. $ 1 \\le n \\le 2 \\cdot 10^5 $  \n2. $ s_i, t_i \\in \\{a, b\\} $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nDetermine the minimum number of swaps (each swapping $ s_i $ with $ t_j $ for some $ i, j $) to make $ s = t $.  \n\n**Feasibility Condition**  \nIt is possible if and only if $ d_{ab} + d_{ba} $ is even.  \n\n**Optimal Operation Count**  \nIf feasible, the minimum number of operations is:  \n$$\nk = \\left\\lfloor \\frac{d_{ab}}{2} \\right\\rfloor + \\left\\lfloor \\frac{d_{ba}}{2} \\right\\rfloor + (d_{ab} \\bmod 2) \\cdot 2\n$$  \nEquivalently:  \n$$\nk = \\frac{d_{ab} + d_{ba}}{2} + (d_{ab} \\bmod 2)\n$$  \n\n**Operation Sequence**  \n- Pair up $ d_{ab} $-type positions: for each pair $ (i, j) $ with $ s_i = a, t_i = b $ and $ s_j = a, t_j = b $, swap $ s_i $ with $ t_j $.  \n- Pair up $ d_{ba} $-type positions: for each pair $ (i, j) $ with $ s_i = b, t_i = a $ and $ s_j = b, t_j = a $, swap $ s_i $ with $ t_j $.  \n- If one $ d_{ab} $ and one $ d_{ba} $ remain, perform two swaps:  \n  1. Swap $ s_i $ (where $ s_i = a, t_i = b $) with $ t_j $ (where $ s_j = b, t_j = a $)  \n  2. Swap $ s_i $ with $ t_i $  \n\nIf infeasible, output $-1$.","simple_statement":null,"has_page_source":false}