题目描述

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

• 对于区间内的第 i 个位置（l ≤ i ≤ r），将该位置的数加上 \[ p \times (i-l)^2 + q \times (i-l). \] 例如，对于操作 (l=1, r=3, p=1, q=2)：
• 第 1 个位置（i=1）：加上 \(1\times0^2 + 2\times0 = 0\)；
• 第 2 个位置（i=2）：加上 \(1\times1^2 + 2\times1 = 1+2 = 3\)；
• 第 3 个位置（i=3）：加上 \(1\times2^2 + 2\times2 = 4+4 = 8\).

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

输入格式

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

输出格式

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

数据范围

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

样例

输入样例

5 2
1 3 1 2
2 5 0 1

输出样例

0 3 9 2 3