题目背景

啊哈哈哈哈！邪恶的数学课代表Swallow_ling要改掉班里同学的数学成绩！只为自己开心！
由于Swallow_ling觉得改别人成绩是一件很爽的事情，所以她想把这份快乐分享给你。
请你写个代码享受吧！

题目描述

Swallow_ling会给某些同学的成绩加分或减分。
当然，她会告诉你每个同学的成绩。
还有，因为她觉得事情太多快乐就消失了，所以她会把减去一个数用加上一个负数表示。
她想知道最后最低的成绩是多少，然后狠狠嘲笑他。

输入格式

第一行有两个整数 $n$，$p$，代表学生数与改动分数的次数。

第二行有 $n$ 个数，$a_1 \sim a_n$，代表各个学生的初始成绩。

接下来 $p$ 行，每行有三个数，$x$，$y$，$z$，代表给第 $x$ 个到第 $y$ 个学生每人改动 $z$ 分。

输出格式

输出$1$行，每行$n$个数，表示行动后最低的成绩。

样例

3 2
1 1 1
1 2 1
2 3 1

2

数据范围

对于 $10\%$ 的数据，有 $n \le 10^3$。

对于 $30\%$ 的数据，有 $n \le 10^4$。

对于 $50\%$ 的数据，有 $n \le 10^5$。

对于 $100\%$ 的数据，有 $n \le 5\times 10^6$，$p \le n$，学生初始成绩 $\le 100$，$-100 \le z \le 100$。

说明/提示

一道很简单的差分题，一点新意都没有。（差评！）