# Thinking problem -- the application of backward order difference

## Title Description

Xiaoma is a good one who loves line trees.
Xiaoma's grandfather, Ma ye, was beaten by Xiaoma in the game, so he became angry and decided to give Xiaoma such a data structure problem:
Given an array AA of length nn, the value of each entry at the beginning is 00.
The following two operations are supported, totaling mm operations:
1 lr1lr: add the value of each term of Al ∼ ArAl ∼ Ar to 11.
2 lr2lr: perform all operations with the operation number in [l,r][l,r] once, to ensure that rr is less than the number of the current operation.
After mm operations, you should tell Ma ye what the AA array looks like.
Since the answer may be large, you only need to output the value of each number in array AA in the sense of modulus 109 + 7109 + 7.

## Enter a description:

`The first row has two numbers, n,mn,m, which respectively represent the array length and the number of operations.Next mm lines, each line has three numbers of opt,l,ropt,l,r, representing an operation.`

## Output Description:

`Output a total of nn lines, indicating the value of A1 ∼ AnA1 ∼ An after mm operations.`
Example 1

copy
```4 3
1 1 3
2 1 1
1 1 3```

## output

copy
`3 3 3 0`

## Remarks:

`For 100% data, 1 ≤ n ≤ 105,1 ≤ m ≤ 1051 ≤ n ≤ 105,1 ≤ m ≤ 105.`

## The code + comments are as follows:

```//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include<sstream>
#include<iterator>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<list>
#include<set>

using namespace std;
typedef double dou;
typedef long long ll;
typedef pair<int, int> pii;

#define pai acos(-1.0)
#define M 200005
#define inf 1e18
#define mod 1000000007
#define left k<<1
#define right k<<1|1
#define W(a) while(a)
#define ms(a,b) memset(a,b,sizeof(a))

struct Data
{
ll Opt, L, R;
}num[M];//operation

ll n, m, pos, pre;
ll ans[M], cnt[M];//ans Is a differential sequence. cnt Is the number of operations

void init()
{
ms(cnt, 0);
ms(ans, 0);
pos = pre = 0;
cnt[m] = 1;//We know that the number of last operations must be one
}

int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> num[i].Opt >> num[i].L >> num[i].R;//Save the operation
}
init();
for (int i = m; i >= 1; i--)
{
pos += cnt[i];//Differential get operation times
pos = (pos + mod) % mod;
if (num[i].Opt == 1)
{
ans[num[i].L] += pos;
ans[num[i].R + 1] -= pos;
}
else
{
cnt[num[i].R] += pos;
cnt[num[i].L - 1] -= pos;
}
}
for (int i = 1; i <= n; i++)
{
pre += ans[i];
cout << (pre + mod) % mod<<' ' ;
}
return 0;
}```