题目描述

给定一个长度为 n 的数组（下标从 1 到 n，初始所有元素均为 0）。现有 m 次操作，每次操作给出 5 个整数 l, r, a, d, k，表示对区间 [l, r] 内的每个位置进行加法操作，具体更新规则如下：

• 对于区间内的第 i 个位置（l ≤ i ≤ r），将该位置的数加上 \[ a + (i-l)\times d + (i-l)^2 \times k. \] 例如，对于操作 (l=1, r=3, a=1, d=2, k=1)：
• 第 1 个位置（i=1）：加上 \(1 + 0\cdot 2 + 0^2\cdot1 = 1\)；
• 第 2 个位置（i=2）：加上 \(1 + 1\cdot2 + 1^2\cdot1 = 1+2+1 = 4\)；
• 第 3 个位置（i=3）：加上 \(1 + 2\cdot2 + 2^2\cdot1 = 1+4+4 = 9\).

多个操作的更新互相叠加。请你利用多重差分数组的思想（需要使用 3 个差分数组）快速处理所有操作，并输出最终数组的所有元素。

输入格式

• 第一行包含两个正整数 n 和 m，表示数组的长度和操作的次数。
• 接下来 m 行，每行包含 5 个整数 l, r, a, d, k，表示一次区间加权更新操作。

输出格式

输出一行 n 个整数，依次表示最终数组的各个元素，数字之间用空格隔开。

数据范围

• \(1 \leq n, m \leq 10^7\)
• 对于每个操作，1 ≤ l ≤ r ≤ n；更新参数 a, d, k 的绝对值不超过 1000。

样例

输入样例

5 2
1 3 1 2 1
2 5 2 1 0

输出样例

1 6 12 4 5