503012 - 区间操作2

【题目描述】区间操作2(region2) 有一个长度为n的全0序列。 这个序列支持两种操作: (1)对区间 L~R每个数增加1; (2)对区间 L~R第一个数增加 1,第二个数增加2,…,第R-L+1个数字增加 R-L+1。 请输出操作m次后的序列。

Input

输入第一行包含两个数字 n和m (1≤n,m≤1e5)。 第2到第 m+1行每行包括 3 个数字 op L R,op为1时执行操作1,否则执行操作2(P≤1e5)。

Output

输出n个数字,代表操作后的序列。

Examples

Input

10 3
1 1 10
2 1 10
1 1 5

Output

3 4 5 6 7 7 8 9 10 11

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题