{"raw_statement":[{"iden":"statement","content":"_Mathematician Pang_ learned Dirichlet convolution during the previous camp. However, compared with deep reinforcement learning, it's too easy for him. Therefore, he did something special. \n\nIf $f, g : {1, 2, \\\\dots, n} arrow.r ZZ$ are two functions from the positive integers to the integers, the Dirichlet convolution $f * g$ is a new function defined by: $$(f * g)(n) =\\sum_{d \\mid n}f(d)g ({\\frac {n}{d}}) .$$\n\nWe define the $k$-th power of an function $g = f^k$ by $$ f^{k}=\\underbrace {f * \\dots * f} _{k~{\\textrm {times}}}.$$\n\nIn this problem, we want to solve the inverse problem: Given $g$ and $k$, you need to find a function $f$ such that $g = f^k$.\n\nMoreover, there is an additional constraint that $f (1)$ and $g (1)$ must equal to $1$. And all the arithmetic operations are done on $FF_p$ where $p = 998244353$, which means that in the Dirichlet convolution, $(f * g) (n) = (sum_(d mid n) f (d) g (frac(n, d))) bmod p$.\n\nThe first line contains two integers $n$ and $k med (2 <= n <= 10^5, 1 <= k < 998244353)$ .\n\nThe second line contains n integers $g (1), g (2),..., g (n)$ ($0 <= g (i) < 998244353, g (1) = 1$).\n\nIf there is no solution, output $-1$.\n\nOtherwise, output $f (1), f (2),..., f (n)$ ($0 <= f (i) < 998244353, f (1) = 1$). If there are multiple solutions, print anyone.\n\n"},{"iden":"input","content":"The first line contains two integers $n$ and $k med (2 <= n <= 10^5, 1 <= k < 998244353)$ .The second line contains n integers $g (1), g (2),..., g (n)$ ($0 <= g (i) < 998244353, g (1) = 1$)."},{"iden":"output","content":"If there is no solution, output $-1$.Otherwise, output $f (1), f (2),..., f (n)$ ($0 <= f (i) < 998244353, f (1) = 1$). If there are multiple solutions, print anyone."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ p = 998244353 $.  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^5 $, $ 1 \\leq k < p $.  \nLet $ g: \\{1, 2, \\dots, n\\} \\to \\mathbb{Z}/p\\mathbb{Z} $ be a function with $ g(1) = 1 $.  \nLet $ f: \\{1, 2, \\dots, n\\} \\to \\mathbb{Z}/p\\mathbb{Z} $ be the unknown function with $ f(1) = 1 $, such that $ g = f^{*k} $, where $ f^{*k} $ denotes the $ k $-fold Dirichlet convolution of $ f $ with itself.\n\n**Constraints**  \n1. $ g(i) \\in \\mathbb{Z}/p\\mathbb{Z} $ for all $ i \\in \\{1, \\dots, n\\} $, and $ g(1) = 1 $.  \n2. $ f(1) = 1 $.  \n3. All operations are performed modulo $ p $.  \n4. For all $ m \\in \\{1, \\dots, n\\} $:  \n   $$\n   g(m) = \\sum_{d \\mid m} f(d) \\cdot f^{*(k-1)}\\left(\\frac{m}{d}\\right) \\mod p\n   $$\n\n**Objective**  \nFind a function $ f $ satisfying $ f^{*k} = g $, or output $-1$ if no such $ f $ exists.","simple_statement":"Given a function $ g $ and an integer $ k $, find a function $ f $ such that $ f^k = g $, where $ f^k $ means $ f $ convolved with itself $ k $ times using Dirichlet convolution. All operations are modulo $ 998244353 $, and $ f(1) = g(1) = 1 $. If no such $ f $ exists, output $-1$.","has_page_source":false}