#1241. 末影箱

末影箱

题目描述

小核桃捡到了 nn 个可以传送 eggy 的末影箱,他把这 nn 个末影箱围成了一个环,按顺时针编号分别为 1,2,,n1,2,\cdots,n,每个末影箱都可以向相邻末影箱传送 eggy。小核桃在 ii 号末影箱上放了 aia_i 只 eggy,接下来他将进行 qq 次操作,如果每次选择 xx 号箱(当然,箱中 eggy 数 2\ge 2)传送 kk 步,则会有两只 eggy 分别从 xx 号箱出发,向左右两边传送 kk 步。

比如,一共 55 个末影箱,选择 11 号箱传送 22 步,则会有 11 只 eggy 从 11 号传送到 22 号又到 33 号,还有 11 只 eggy 从 11 号传送到 55 号再到 44 号。

问做了 qq 次操作后,每个末影箱上有多少只eggy?

输入格式

第一行包括两个整数 nnqq

第二行包括 nn 个整数 aia_i

接下来的 qq 行,每行两个整数 xxkk

输出格式

一行,nn 个整数,代表最后每个末影箱上的 eggy 数量。

样例 #1

样例输入 #1

5 2
3 4 2 4 3
1 2
4 1

样例输出 #1

1 4 4 3 4

key

对于 100%100\% 的数据,2n1052\le n\le 10^50q1050\le q\le 10^51ai1091 \le a_i \le 10^9, 1xn1 \le x \le n, 1k<n1 \le k \lt n