{"problem":{"name":"[ICPC 2021 Macao R] Pass the Ball!","description":{"content":"There are $n$ children playing with $n$ balls. Both children and balls are numbered from $1$ to $n$. Before the game, $n$ integers $p_1, p_2, \\cdots, p_n$ are given. In each round of the game, child ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9660"},"statements":[{"statement_type":"Markdown","content":"There are $n$ children playing with $n$ balls. Both children and balls are numbered from $1$ to $n$.\n\nBefore the game, $n$ integers $p_1, p_2, \\cdots, p_n$ are given. In each round of the game, child $i$ will pass the ball he possesses to child $p_i$. It is guaranteed that no child will pass his ball to himself, which means $p_i \\neq i$. Moreover, we also know that after each round, each child will hold exactly one ball.\n\nLet $b_i$ be the ball possessed by child $i$. At the beginning of the game, child $i$ ($1 \\le i \\le n$) will be carrying ball $i$, which means $b_i=i$ initially. You're asked to process $q$ queries. For each query you're given an integer $k$ and you need to compute the value of $\\sum\\limits_{i=1}^{n} i \\times b_i$ after $k$ rounds.\n\n## Input\n\nThere is only one test case for each test file.\n\nThe first line of the input contains two integers $n$ ($2 \\le n \\le 10^5$) and $q$ ($1 \\le q \\le 10^5$), indicating the number of children and the number of queries.\n\nThe second line contains $n$ integers $p_1, p_2, \\cdots, p_n$ ($1 \\le p_i \\le n$) indicating how the children pass the balls around.\n\nFor the following $q$ lines, the $i$-th line contains one integer $k_i$ ($1 \\le k_i \\le 10^9$) indicating a query asking for the result after $k_i$ rounds.\n\n## Output\n\nFor each query output one line containing one integer indicating the answer.\n\n[samples]\n\n## Note\n\nThe sample test case is explained below.\n\n$$\n\\begin{array}{|c|c|c|c|c|c|} \\hline \\textbf{Round} & \\textbf{b1} & \\textbf{b2} & \\textbf{b3} & \\textbf{b4} & \\textbf{Answer} \\\\\\hline \n1 & 3 & 1 & 4 & 2 & 25 \\\\\\hline\n2 & 4 & 3 & 2 & 1 & 20 \\\\\\hline\n3 & 2 & 4 & 1 & 3 & 25 \\\\\\hline\n4 & 1 & 2 & 3 & 4 & 30 \\\\\\hline\n\\end{array}\n$$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9660","tags":["2021","多项式","O2优化","快速傅里叶变换 FFT","快速数论变换 NTT","ICPC","澳门"],"sample_group":[["4 4\n2 4 1 3\n1\n2\n3\n4","25\n20\n25\n30"]],"created_at":"2026-03-03 11:09:25"}}