题目描述

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

比如，一共 $5$ 个末影箱，选择 $1$ 号箱传送 $2$ 步，则会有 $1$ 只 eggy 从 $1$ 号传送到 $2$ 号又到 $3$ 号，还有 $1$ 只 eggy 从 $1$ 号传送到 $5$ 号再到 $4$ 号。

问做了 $q$ 次操作后，每个末影箱上有多少只eggy？

输入格式

第一行包括两个整数 $n$ 和 $q$；

第二行包括 $n$ 个整数 $a_i$；

接下来的 $q$ 行，每行两个整数 $x$、$k$。

输出格式

一行，$n$ 个整数，代表最后每个末影箱上的 eggy 数量。

样例 #1

样例输入 #1

5 2
3 4 2 4 3
1 2
4 1

样例输出 #1

1 4 4 3 4

key

对于 $100\%$ 的数据，$2\le n\le 10^5$，$0\le q\le 10^5$， $1 \le a_i \le 10^9$, $1 \le x \le n$, $1 \le k \lt n$。