差分练习

题目描述

给一个数列 $a_1, a_2, \dots, a_n$。

要求支持 $q$ 个操作，每次会给一段区间 $[l, r]$，将 $a_l, a_{l+1}, \dots, a_r$ 全都加上 $1$。

问最后整个数列会变成什么样。

输入格式

第一行两个整数 $n, q$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行两个整数 $l, r$。

输出格式

输出一行 $n$ 个整数，表示答案。

样例输入

5 3
1 2 3 4 5
1 3
2 4
3 5

样例输出

2 4 6 6 6

数据范围

对于 $100\%$ 的数据，保证 $1\le n, q\leq 10^5, 1\leq a_i\leq 10^5, 1 \le l \le r \le n$。