题目描述

小图是 $23$ 级的学生，他刚刚学习了一些算法，于是他找到了他的老师，想让老师考验考验他。 老师给小图一个长度为 $n$ 的下标从 $1$ 开始的数组 $a$，以及 $m$ 次操作。 在每次操作中，老师给出四个正整数 $x, c, d, l$ ，希望小图能够在数组下标为 $x$ 的位置上，加上一个以 $c$ 为首项， $d$ 为公差， 长度为 $l$ 的等差数列，即若假设加上的等差数列为数组 $b$，则每次操作是 $a_x + b_1, a_{x + 1} + b_2,..., a_{x + l - 1} + b_l$，并且如果等差数列后面的项超过数组长度，超出部分忽略不计。 小图需要告诉老师 $m$ 次操作完成后，数组每一个元素的值。 小图觉得这个问题太难了，于是交给了善于编程的你。

输入描述

输入第一行包含两个整数 $n, m$，分别表示数组 $a$ 的长度，以及操作次数。

第二行有 $n$ 个整数 $a_1,a_2,...,a_n$。

接下来的 $m$ 行，每行四个正整数 $x, c, d, l$ ，表示每次操作的内容。

输出描述

输出一行 $n$ 个整数表示操作后数组的值 $a_1,a_2,...,a_n$。

样例

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

2 6 6 8 5

数据范围

$3 \leq l \leq n, m \leq 2 \cdot 10^5, 1 \leq x \leq n, 1 \leq c, d, a_i \leq 10^4$。