题目描述

有一个整型数组 $a$，长度为 $n$，初始时已给定每个元素的值。接下来有 $q$ 次修改操作，每次修改给出两个端点 $L$ 和 $R$，表示将数组下标 $L$ 到 $R$（包含两端）的所有元素值增加 $1$。请求出经过 $q$ 次修改后数组的最终结果。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示数组的长度和修改次数。
第二行包含 $n$ 个整数，表示数组 $a$ 的初始值。
接下来 $q$ 行，每行包含两个整数 $L$ 和 $R$，表示一次区间加 $1$ 操作。

输出格式

输出一行 $n$ 个整数，用空格隔开，表示经过 $q$ 次修改后数组的结果。

样例

5 2
1 2 3 4 5
1 2
2 3

2 4 4 5 5

样例解释

初始数组为 $[1, 2, 3, 4, 5]$。
第一次操作：区间 $[1, 2]$ 加 $1$，变为 $[2, 3, 3, 4, 5]$。
第二次操作：区间 $[2, 3]$ 加 $1$，变为 $[2, 4, 4, 5, 5]$。

数据范围

• $1 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$
• $1 \le L \le R \le n$
• 初始数组元素值在 $32$ 位有符号整数范围内。