Cyborg Jenish is angry.

He has so much rage that he decided to go on a demolition spree for $Q$ days.

There are $N$ cities in his world numbered $1$ to $N$, in a row from left to right. That is the $i^{th}$ city from left side is city-$i$ where $1 ≤ i ≤ N$. The supreme leader of the world is VSM and there are infinite statues of VSM in each city.

On each day Jenish chooses two cities $L$ and $R$. He starts at city-$L$ and moves along the row towards right side till he reaches the city-$R$. In city-$L$ he destroys $1$ statue, in the next city (i.e. city-$L+1$) he destroys $2$ statues, and so on till city-$R$ where he destroys $R-L+1$ statues. In other words, he destroys $i-L+1$ statues in the $i^{th}$ city ( $L≤ i≤ R$ ).

Find the total number of VSM statues he destroyed in each city after $Q$ days.

------ Input: ------
The first line contains an integer $T$, denoting the number of test cases.
The first line of each test case, contains two space-separated integers $N$ and $Q$ denoting the number of cities in his world and the number of days he goes on a demolition spree respectively.
The $i^{th}$ line of next $Q$ lines of each test case contains two space-separated integers $L$ and $R$ denoting the starting city and the ending city respectively on $i^{th}$ day.

------ Output: ------
For each test case, output a single line containing $N$ space-separated integers.
The $i^{th}$ integer should denote the total number of VSM statues destroyed by cyborg Jenish in the city-$i$ after $Q$ days.

------ Constraints: ------
$1 ≤ T ≤ 10^{3}$
$ 1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$1≤ L ≤ R ≤ N$
The sum of $N$ over all test cases is less than $10^{6}$
The sum of $Q$ over all test cases is less than $10^{6}$

----- Sample Input 1 ------
2
5 3
1 3
1 2
4 5
2 1
1 1
----- Sample Output 1 ------
2 4 3 1 2
1 0
----- explanation 1 ------
In the first test case, the cyborg does the following:
- Starts at city-1 and goes till city-3, hence destroys $1$ statue in city-1, $2$ in city-2, and $3$ in city-3.
- Starts at city-1 and goes till city-2, hence destroys $1$ statue in city-1 and $2$ in city-2.
- Starts at city-4 and goes till city-5, hence destroys $1$ statue in city-4 and $2$ in city-5.
- Hence he destroyed total $2$ statues in city-1, $4$ in city-2, $3$ in city-3, $1$ in city-4, and $2$ in city-5.

见题面

见题面