题目描述

在边境，每天都会安排夜间巡逻的战士，目前已经安排好了 $n$ 天的巡逻人数。

但是最近局势不太平，会不定期从其他地方抽调一名战士来支援边境的巡逻任务，支援一段时间后离开。

现在你知道了原本各天巡逻的人数，并且提供给你一份调配记录，你需要计算出各天巡逻的实际人数是多少。

输入格式

第一行两个整数 $n$ 和 $q$, 分别代表总天数和调配记录数量

第二行 $n$ 个整数，依次表示每一天的巡逻人数

接下来的 $q$ 行，每行两个整数 $begin$ 和 $end$，表示第 $begin$ 天抽调了一名战士来支援，并且该战士在第 $end$ 天之后会离开。

输出格式

一行输出 $n$ 个整数，每个整数表示实际巡逻的战士数量

样例数据

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

4 5 6 6 3

样例解释

原定5天分别有 3、3、4、4、3个战士巡逻

第一个抽调过来支援的战士从第3天到第4天巡逻

第二个抽调过来支援的战士从第1天到第2天巡逻

第三个抽调过来支援的战士从第2天到第4天巡逻

数据范围

对于40%的数据，$1 \le n,q \le 10$

对于100%的数据，$1 \le n \le 50000, 1\le q \le 100000$，$begin$ 和 $end$ 保证在 $1\sim n$ 范围内且 $begin \le end$