#ABC340E. 播棋

播棋

AT_abc340_e [ABC340E] Mancala 2

题目描述

\hspace{15pt}有 nn 个箱子,编号从 00 到 n−1n-1。最初,第 ii 个箱子中有 aia_i 个球。

\hspace{15pt}高桥按照 i=1,2,…,mi = 1, 2, \dots, m 的顺序,依次执行 mm 次操作。第 ii 次操作的流程如下:

1. {\hspace{20pt}}_\texttt{1.}\,将计数器 cc 设为 00;

2. {\hspace{20pt}}_\texttt{2.}\,取出编号为 bib_i 的箱子中的全部球,拿在手中;

3. {\hspace{20pt}}_\texttt{3.}\,只要手中还至少有 11 个球,就重复以下过程:

∘ \hspace{38pt}\circ\,将 cc 的值增加 11;

∘ \hspace{38pt}\circ\,从手中取出 11 个球,放入编号为 (bi+c) mod n\left(b_i + c\right) \bmod n 的箱子。

\hspace{15pt}其中 u mod nu \bmod n 表示 uu 除以 nn 得到的余数。

\hspace{15pt}请在所有操作结束后,输出每个箱子中球的数量。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦2×105)n, m \left(1 \leqq n, m \leqq 2 \times 10^5\right) 分别代表箱子数量和操作次数。

\hspace{15pt}第二行输入 nn 个整数 $a_0, a_1, \dots, a_{n-1} \left(0 \leqq a_i \leqq 10^9\right)$ 代表每个箱子中初始的球数。

\hspace{15pt}第三行输入 mm 个整数 b1,b2,…,bm(0≦bi<n)b_1, b_2, \dots, b_m \left(0 \leqq b_i < n\right) 代表每次操作取球的箱子编号。

输出格式

\hspace{15pt}在一行上输出 nn 个整数 x0,x1,…,xn−1x_0, x_1, \dots, x_{n-1},相邻两个整数之间用一个空格隔开,其中 xix_i 代表所有操作结束后第 ii 个箱子中的球数。

测试样例

5 3
1 2 3 4 5
2 4 0
0 4 2 7 2

样例 1 解释

\hspace{15pt}初始时五个箱子中的球数依次为 {1,2,3,4,5}\{1, 2, 3, 4, 5\}(按编号 0∼40 \sim 4 排列)。

∙ \hspace{23pt}\bullet\,第 11 次操作取编号为 22 的箱子,其中有 33 个球,依次放入编号 3,4,03, 4, 0 的箱子,球数变为 {2,2,0,5,6}\{2, 2, 0, 5, 6\};

∙ \hspace{23pt}\bullet\,第 22 次操作取编号为 44 的箱子,其中有 66 个球,先给每个箱子各 11 个(共 55 个),剩下的 11 个放入编号 00 的箱子,球数变为 {4,3,1,6,1}\{4, 3, 1, 6, 1\};

∙ \hspace{23pt}\bullet\,第 33 次操作取编号为 00 的箱子,其中有 44 个球,依次放入编号 1,2,3,41, 2, 3, 4 的箱子,球数变为 {0,4,2,7,2}\{0, 4, 2, 7, 2\}。

\hspace{15pt}因此输出 0,4,2,7,20, 4, 2, 7, 2。

3 10
1000000000 1000000000 1000000000
0 1 0 1 0 1 0 1 0 1
104320141 45436840 2850243019
1 4
1
0 0 0 0
1

样例 3 解释

\hspace{15pt}只有一个编号为 00 的箱子。每次取出其中的 11 个球后,因为 (0+1) mod 1=0\left(0 + 1\right) \bmod 1 = 0,这个球又被放回编号为 00 的箱子,因此每次操作后箱子中始终有 11 个球,最终输出 11。