{"raw_statement":[{"iden":"statement","content":"There are $k$ piles of stones in a circle, labeled from $0$ to $(k -1)$, where the number of the stones in each pile is $n$ initially.\n\nYou can do some operations in rounds. The operation of the $i$-th round is to change the pile labeled $((i -1) bmod k)$, which allows you to remove some (at least one) stones from this pile, such that the old number of stones in this pile is a multiple of the new number. It also implies that you need to keep at least one stone in the pile after this operation.\n\nThe game will end if at least one pile contains only one stone. Given the positive integers $n$ and $k$, your task is to calculate for each pile, the number of different ways to do operations which can cause the game to end so that this pile is the last changed one.\n\nThe integer $n$ can be gigantic, so $n$ would be given using its prime factorization, in other words, assuming that $n = product_{i = 1}^m p_i^(e_i)$ for distinct prime numbers $p_1$, $p_2$, $\\\\dots$, $p_m$, $m$ and $(p_i, e_i)$ would be given instead of $n$.\n\nThe answer may be fairly large, so you should output the answer modulo $985661441$ instead.\n\nThe input contains multiple (about $200$) test cases.\n\nFor each test case, the first line contains two integers $m$, $k$ ($1 <= m, k <= 10$).\n\nThe $i$-th line of the next $m$ lines contains two integers $p_i$, $e_i$ ($2 <= p_i <= 10^9$, $e_i >= 1$). It is guaranteed that $p_1$, $p_2$, $\\\\dots$, $p_m$ are distinct prime numbers and $sum_{i = 1}^m e_i <= 10^5$ for each test case.\n\nIt is also guaranteed that no more than $5$ test cases satisfy that $sum_{i = 1}^m e_i >= 10^4$.\n\nFor each test case, output \"_Case #x: y$\"\"_0$ y$\"\"_1$ $\\\\dots$ y$\"\"_(k -1)$_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y_i$ denotes the number of different ways modulo $985661441$ for the pile labeled $i$ in the corresponding case.\n\n"},{"iden":"input","content":"The input contains multiple (about $200$) test cases.For each test case, the first line contains two integers $m$, $k$ ($1 <= m, k <= 10$).The $i$-th line of the next $m$ lines contains two integers $p_i$, $e_i$ ($2 <= p_i <= 10^9$, $e_i >= 1$). It is guaranteed that $p_1$, $p_2$, $\\\\dots$, $p_m$ are distinct prime numbers and $sum_{i = 1}^m e_i <= 10^5$ for each test case.It is also guaranteed that no more than $5$ test cases satisfy that $sum_{i = 1}^m e_i >= 10^4$."},{"iden":"output","content":"For each test case, output \"_Case #x: y$\"\"_0$ y$\"\"_1$ $\\\\dots$ y$\"\"_(k -1)$_\" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y_i$ denotes the number of different ways modulo $985661441$ for the pile labeled $i$ in the corresponding case."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of people, with $ 2 \\leq n \\leq 10^4 $.  \nLet $ A = (a_1, a_2, \\dots, a_{2n}) $ be a sequence of $ 2n $ positive integers representing slice sizes, where $ 1 \\leq a_i \\leq 10^9 $.\n\n**Constraints**  \nEach person consumes exactly two slices.  \nEach slice is assigned to exactly one person.\n\n**Objective**  \nPartition $ A $ into $ n $ disjoint pairs $ (a_i, a_j) $ such that the maximum difference between the sums of any two pairs is minimized.  \nLet $ S = \\{ s_1, s_2, \\dots, s_n \\} $, where $ s_k = a_{i_k} + a_{j_k} $ is the total pizza consumed by person $ k $.  \nCompute:  \n$$\n\\min \\left( \\max_{1 \\leq k \\leq n} s_k - \\min_{1 \\leq k \\leq n} s_k \\right)\n$$","simple_statement":"You have 2n pizza slices. Each of n people eats exactly 2 slices.  \nFind the minimum possible difference between the person who eats the most and the person who eats the least.","has_page_source":false}