题目描述

给定一个长度为 n 的数列，数列初始时所有元素的值均为 0。接下来需要执行 q 次区间操作，每次操作给定两个整数 l 和 r（表示数列的区间左、右端点），要求对该区间 [l, r] 内的元素依次加上一个等差数列：第 l 个位置加 1、第 l+1 个位置加 2、……、第 r 个位置加 r-l+1（即等差数列的首项为 1，末项为区间长度 r-l+1，公差为 1）。 完成所有操作后，请输出最终的数列。

输入格式

第一行输入两个整数 n 和 q（1 ≤ n ≤ 1e5，1 ≤ q ≤ 100），分别表示数列的长度和操作次数； 接下来 q 行，每行输入两个整数 l 和 r（1 ≤ l ≤ r ≤ n），表示本次操作的区间范围 [l, r]。

输出格式

输出一行，包含 n 个整数，依次表示最终数列中第 1 到第 n 个位置的元素值，整数之间用空格分隔。

样例

5 1
1 5

1 2 3 4 5

样例解释

初始数列为 [0, 0, 0, 0, 0]； 执行 1 次操作，区间为 [1, 5]，需要在该区间依次加上等差数列 1, 2, 3, 4, 5： 第 1 个位置：0 + 1 = 1 第 2 个位置：0 + 2 = 2 第 3 个位置：0 + 3 = 3 第 4 个位置：0 + 4 = 4 第 5 个位置：0 + 5 = 5 最终数列为 [1, 2, 3, 4, 5]。