题目描述

一年一次的蟠桃大会热闹非凡，今年王母娘娘共邀请了 $n$ 位仙家来赴蟠桃大会，并且为每位仙家都安排了一定初始数量的蟠桃，但是害怕有人不够吃，所以又进行了 $m$ 次添加蟠桃的操作，每个操作包含三个整数 $l,r,x$，表示将序列中 $[l,r]$ 之间的每个位置加上 $x$ 个蟠桃，请你输出最终每位仙家吃到的蟠桃数。

输入格式

第一行包含两个整数 $n,m$ $(1 \le n,m \le 50000)$。

第二行包含 $n$ 个整数，表示初始蟠桃数量。

接下来 $m$ 行，每行包含三个整数 $l,r,x$，表示一次操作 $(l < r \le n, 1 \le x \le 100)$。

输出格式

共一行，包含 $n$ 个整数，表示最终蟠桃数量。

样例

输入样例1

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例1

3 4 5 3 4 2

数据范围

$1 \le n,m \le 50000$，$1 \le x \le 100$，$l < r \le n$。