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.

Difficulty: HARD
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	queries = [list(map(int, input().split())) for _ in range(q)]
	prefix_sum = [0] * (n + 1)
	for (l, r) in queries:
		prefix_sum[l - 1] += 1
		prefix_sum[r] -= 1
	for j in range(1, n):
		prefix_sum[j] += prefix_sum[j - 1]
	for (l, r) in queries:
		prefix_sum[r] -= r - l + 1
	for i in range(1, n):
		prefix_sum[i] += prefix_sum[i - 1]
	print(*prefix_sum[:n])


t = int(input())
while t > 0:
	(n, q) = map(int, input().split())
	ck = []
	for _ in range(q):
		(a, b) = map(int, input().split())
		ck.append([a, b])
	l = [0 for i in range(n + 3)]
	for i in ck:
		(a, b) = i
		l[a] += 1
		l[b + 1] += a - b - 2
		l[b + 2] += b - a + 1
	for i in range(1, len(l)):
		l[i] = l[i] + l[i - 1]
	for i in range(1, len(l)):
		l[i] = l[i] + l[i - 1]
	print(*l[1:len(l) - 2])
	t -= 1


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = [0] * (n + 2)
	queries = []
	for _ in range(q):
		(L, R) = map(int, input().split())
		queries.append((L, R))
		a[L] += 1
		a[R + 1] -= 1
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	for (L, R) in queries:
		a[R + 1] -= R - L + 1
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	for i in range(1, n + 1):
		print(a[i], end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	des = [0] * (n + 1)
	ps = []
	for _ in range(q):
		(l, r) = map(int, input().split())
		ps.append((l - 1, r))
		des[l - 1] += 1
		des[r] -= 1
	for i in range(1, len(des)):
		des[i] += des[i - 1]
	for (l, r) in ps:
		des[r] -= r - l
	for i in range(1, len(des)):
		des[i] += des[i - 1]
	des.pop(-1)
	print(*des)


def query(l, r):
	a[l] += 1
	c[r + 1] += 1
	b[r + 1] -= r - l + 1

def answer():
	inc = 0
	for i in range(1, n + 1):
		if a[i]:
			inc += a[i]
		if b[i]:
			inc -= c[i]
		a[i] = a[i - 1] + b[i] + inc
	return a[1:n + 1]
for T in range(int(input())):
	(n, q) = map(int, input().split())
	a = [0] * (n + 2)
	b = [0] * (n + 2)
	c = [0] * (n + 2)
	for x in range(q):
		(l, r) = map(int, input().split())
		query(l, r)
	print(*answer())


tt = int(input())
for _ in range(tt):
	(n, q) = [int(i) for i in input().split()]
	queries = []
	a = [0] * (n + 1)
	(l, r) = (0, 0)
	for i in range(q):
		(l, r) = [int(i) for i in input().split()]
		queries.append((l, r))
		a[l] += 1
		if r + 1 <= n:
			a[r + 1] -= 1
	for i in range(2, n + 1):
		a[i] += a[i - 1]
	for i in range(q):
		(l, r) = (queries[i][0], queries[i][1])
		if r + 1 <= n:
			a[r + 1] -= r - l + 1
	for i in range(2, n + 1):
		a[i] += a[i - 1]
	for i in range(1, n + 1):
		print(a[i], end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = [0] * (n + 1)
	b = []
	for _ in range(q):
		(l, r) = map(int, input().split())
		a[l - 1] += 1
		a[r] -= 1
		b.append([l - 1, r])
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	for (l, r) in b:
		a[r] -= r - l
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	a.pop()
	print(*a)


t = int(input())
while t:
	t = t - 1
	(n, q) = map(int, input().split())
	l1 = [0 for i in range(n + 1)]
	l2 = [0 for i in range(n + 1)]
	for i in range(q):
		(a, b) = map(int, input().split())
		l1[a - 1] += -a + 2
		l2[a - 1] += 1
		l1[b] -= -a + 2
		l2[b] -= 1
	for i in range(1, n):
		l1[i] += l1[i - 1]
		l2[i] += l2[i - 1]
	for i in range(n):
		l2[i] = l1[i] + i * l2[i]
	print(*l2[:n])


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	difArray = [[0, 0] for i in range(n + 2)]
	for i in range(q):
		(l, r) = map(int, input().split())
		difArray[l][0] += 1
		difArray[r + 1][0] -= 1
		difArray[r + 1][1] -= r - l + 1
	counter = 0
	ans = [0] * n
	pre = 0
	for i in range(1, n + 1):
		counter += difArray[i][0]
		ans[i - 1] = pre + counter + difArray[i][1]
		pre = ans[i - 1]
	print(*ans)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	sol = [0] * n
	left = [0] * n
	right = defaultdict(lambda : [])
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		left[l] += 1
		right[r].append(r - l + 1)
	tot = [0] * n
	sol[0] = left[0]
	tot[0] = left[0] - len(right[0])
	for i in range(1, n):
		sol[i] = left[i] + sol[i - 1] + tot[i - 1]
		for el in right[i - 1]:
			sol[i] -= el
		tot[i] = tot[i - 1] + left[i] - len(right[i])
	print(' '.join([str(i) for i in sol]))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [0] * (n + 3)
	d = []
	for i in range(q):
		(a, b) = map(int, input().split())
		d.append((a, b))
		arr[a] += 1
		arr[b + 1] -= 1
	for i in range(1, n + 1):
		arr[i] += arr[i - 1]
	for i in d:
		arr[i[1] + 1] -= i[1] + 1 - i[0]
	for i in range(1, n + 1):
		arr[i] += arr[i - 1]
	for i in range(1, n + 1):
		print(arr[i], end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = [0 for i in range(n + 2)]
	k = []
	for i in range(q):
		(u, v) = map(int, input().split())
		l[u] += 1
		l[v + 1] -= 1
		k.append([u, v + 1])
	for i in range(1, n + 1):
		l[i] += l[i - 1]
	for i in k:
		l[i[1]] -= i[1] - i[0]
	for i in range(1, n + 1):
		l[i] += l[i - 1]
	for i in range(1, n + 1):
		print(l[i], end=' ')
	print()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = [0] * n
	b = [0] * (n + 1)
	c = [0] * (n + 1)
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		a[l] += 1
		b[r] += r - l
		c[r] += 1
	tot = cnt = 0
	for i in range(n):
		cnt += a[i] - c[i]
		tot += cnt - b[i]
		print(tot, end=' ')
	print()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = [0] * n
	b = [0] * (n + 1)
	c = [0] * (n + 1)
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		a[l] += 1
		b[r] += r - l
		c[r] += 1
	tot = cnt = 0
	for i in range(n):
		cnt += a[i] - c[i]
		tot += cnt - b[i]
		print(tot, end=' ')
	print()


for k in range(int(input())):
	a = list(map(int, input().split()))
	n = a[0]
	q = a[1]
	s = [0] * 100002
	e = [0] * 100002
	for j in range(q):
		b = list(map(int, input().split()))
		s[b[0]] += 1
		s[b[1] + 1] -= 1
		e[b[1] + 1] -= b[1] - b[0] + 1
	for i in range(1, n + 1):
		s[i] += s[i - 1]
	for i in range(1, n + 1):
		e[i] += e[i - 1] + s[i]
	for i in range(1, n + 1):
		print(e[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().split()))
	d = dict()
	p = [0] * (n + 2)
	m = [0] * (n + 2)
	k = [0] * (n + 2)
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		p[l] += 1
		m[r + 1] += 1
		k[r + 1] += r - l + 1
	h = []
	g = []
	curr = 0
	times = 0
	for i in range(1, n + 1):
		times += p[i]
		times -= m[i]
		if m[i]:
			curr -= k[i]
		h.append(times)
		g.append(curr)
		curr += times
		print(curr, end=' ')
	print('')


import sys
import math
import bisect
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def printlist(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')
t = inp()
for _ in range(t):
	(N, Q) = invr()
	d = [[0, 0] for i in range(N)]
	for _ in range(Q):
		(L, R) = invr()
		if R < N:
			d[R][0] += -(R - L + 2)
			d[R][1] += -1
		d[L - 1][0] += 1
		d[L - 1][1] += 1
	c = 0
	x = 0
	for i in range(1, N):
		d[i][0] += d[i - 1][0] + d[i - 1][1]
		d[i][1] += d[i - 1][1]
	x = []
	for i in range(N):
		x.append(d[i][0])
	print(*x)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [0] * (n + 2)
	for j in range(q):
		(l, r) = map(int, input().split())
		arr[l - 1] += 1
		arr[r] -= r - l + 2
		arr[r + 1] += r - l + 1
	extra = [0] * n
	extra[0] = arr[0]
	for j in range(1, n):
		extra[j] = extra[j - 1] + arr[j]
	for j in range(1, n):
		extra[j] = extra[j] + extra[j - 1]
	print(*extra)


from sys import stdin, stdout
from collections import *
from math import gcd, floor, ceil

def st():
	return list(stdin.readline().strip())

def li():
	return list(map(int, stdin.readline().split()))

def mp():
	return map(int, stdin.readline().split())

def inp():
	return int(stdin.readline())

def pr(n):
	return stdout.write(str(n) + '\n')
mod = 1000000007
INF = float('inf')

def solve():
	(n, q) = mp()
	l = [0] * (n + 1)
	k = [li() for i in range(q)]
	for i in k:
		(a, b) = i
		l[a - 1] += 1
		l[b] -= 1
	for i in range(1, n):
		l[i] += l[i - 1]
	for i in k:
		(a, b) = i
		l[b] -= b - a + 1
	for i in range(1, n):
		l[i] += l[i - 1]
	print(*l[:-1])
for _ in range(inp()):
	solve()


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	qarr = []
	for i in range(q):
		(a, b) = map(int, input().split())
		qarr.append((a, b))
	a = [0] * (n + 2)
	for i in qarr:
		a[i[0]] += 1
		a[i[1] + 1] -= 1
	for i in range(1, n + 1):
		a[i] += a[i - 1]
	for i in qarr:
		a[i[1] + 1] -= i[1] - i[0] + 1
	for i in range(1, n + 1):
		a[i] += a[i - 1]
	for i in range(1, n + 1):
		print(a[i], end=' ')
	print()


from collections import defaultdict
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	ind = defaultdict(list)
	unique_val = 1
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		ind[l].append(unique_val)
		ind[r + 1].append(-unique_val)
		unique_val += 1
	no_sts = 0
	ispeed = 0
	occ = {}
	for i in range(n):
		for j in ind[i]:
			if j > 0:
				occ[j] = i
				ispeed += 1
			elif j < 0:
				ispeed -= 1
				no_sts -= i - occ[-j]
		no_sts += ispeed
		print(no_sts, end=' ')
	print()


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
tc = 1
tc = L()[0]
for _ in range(tc):
	(n, q) = L()
	op = [0 for i in range(n + 2)]
	cl = [0 for i in range(n + 2)]
	nop = [0 for i in range(n + 2)]
	for queries in range(q):
		(x, y) = L()
		op[x] += 1
		cl[y + 1] -= y - x + 1
		nop[y + 1] -= 1
	A = [0 for i in range(n + 1)]
	curr = 0
	score = 0
	for i in range(1, n + 1):
		curr += op[i] + nop[i]
		score = A[i - 1] + curr + cl[i]
		A[i] = score
	print(*A[1:])
endtime = time.time()


for t in range(int(input())):
	(n, q) = map(int, input().strip().split(' '))
	arr = [[0, 0] for i in range(n + 7)]
	for i in range(q):
		(l, r) = map(int, input().strip().split(' '))
		arr[l][0] += 1
		arr[r + 1][0] -= r - l + 1
		arr[l][1] += 1
		arr[r][1] -= 1
	for i in range(1, n + 1):
		arr[i][0] += arr[i - 1][0] + arr[i - 1][1]
		arr[i][1] += arr[i - 1][1]
	for i in range(1, n + 1):
		print(arr[i][0], end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, q) = [int(p) for p in input().split()]
	v1 = [0] * n
	v2 = [0] * n
	v3 = [0] * n
	v4 = [0] * n
	res = 0
	cnt = 0
	for i in range(q):
		(l, r) = [int(p) for p in input().split()]
		l -= 1
		r -= 1
		v1[r] += r - l + 1
		v2[r] += 1
		if l - 1 > -1:
			v3[l - 1] += 1
	for i in range(n - 1, -1, -1):
		v4[i] = v1[i] - cnt + res
		cnt += v2[i] - v3[i]
		res = v4[i]
	print(*v4)


from math import log2
import sys
sys.setrecursionlimit(10 ** 7)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	m = [0 for i in range(n + 2)]
	inc = m[:]
	distruction = m[:]
	dec = m[:]
	answer = m[:]
	shares = m[:]
	for j in range(k):
		(a, b) = map(int, input().split())
		inc[a] += 1
		dec[b + 1] += 1
		distruction[b + 1] += b - a + 1
	shares[1] = inc[1]
	answer[1] = inc[1]
	for i in range(2, len(shares)):
		shares[i] = shares[i - 1] + inc[i] - dec[i]
	for i in range(2, len(shares)):
		answer[i] = answer[i - 1] + shares[i] - distruction[i]
	ans = answer[1:-1]
	print(*ans)


from collections import Counter
for i in range(int(input())):
	(n, q) = map(int, input().split())
	(s, e, f) = (Counter(), Counter(), Counter())
	for j in range(q):
		(a, b) = map(int, input().split())
		s[a - 1] += 1
		e[b - 1] += 1
		f[b - 1] += b - a + 1
	p = [0] * n
	p[0] = s[0]
	an = s[0] - e[0]
	for j in range(1, n):
		an += s[j]
		p[j] = p[j - 1] - f[j - 1] + an
		an -= e[j]
	print(*p)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = [0] * (n + 1)
	b = [0] * (n + 1)
	for i in range(q):
		(l, r) = map(int, input().split())
		m = r - l + 1
		l -= 1
		r -= 1
		sm = m * (m + 1) // 2
		a[l] += 1
		a[r + 1] -= 1 + m
		b[l] += 1
		b[r + 1] -= 1
	sm = 0
	res = []
	for i in range(n):
		res.append(a[i] + sm)
		sm += b[i]
	for i in range(1, n):
		res[i] += res[i - 1]
	print(*res)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	(start_count, end_count) = ([0] * (n + 1), [0] * (n + 1))
	(start_sum, end_sum) = ([0] * (n + 1), [0] * (n + 1))
	for _ in range(q):
		(l, r) = map(int, input().split())
		start_count[l] += 1
		start_sum[l] += l
		end_count[r] += 1
		end_sum[r] += l
	count = 0
	x = 0
	for i in range(1, n + 1):
		count -= end_count[i - 1]
		x -= end_sum[i - 1]
		count += start_count[i]
		x += start_sum[i]
		print((i + 1) * count - x, end=' ')
	print()


for tc in range(int(input())):
	(N, Q) = map(int, input().split())
	add = [[] for i in range(N)]
	rem = [[] for i in range(N)]
	for i in range(Q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		l = b - a + 1
		add[a].append(1)
		rem[b].append(l)
	ans = []
	currSum = currCnt = 0
	for i in range(N):
		while add[i]:
			currSum += add[i].pop()
			currCnt += 1
		ans.append(currSum)
		while rem[i]:
			currSum -= rem[i].pop()
			currCnt -= 1
		currSum += currCnt
	print(*ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [0] * (n + 2)
	e = [0] * (n + 2)
	for i in range(k):
		(u, v) = map(int, input().split())
		a[u] += 1
		a[v + 1] -= 1
		e[v + 1] += v - u + 1
	s = a[1]
	c = s
	for i in range(2, n + 1):
		s += a[i]
		c += s
		c -= e[i]
		a[i] = c
	print(*a[1:n + 1])


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
(tc,) = inp()
for _ in range(tc):
	(n, q) = inp()
	a = [0] * (n + 1)
	b = [0] * (n + 1)
	for k in range(q):
		(i, j) = inp()
		a[i - 1] += 1
		a[j] -= 1
		b[j] += j - i + 1
	for i in range(1, n + 1):
		a[i] += a[i - 1]
	ans = [0] * n
	cur = 0
	for i in range(n):
		cur = cur - b[i] + a[i]
		ans[i] = cur
	print(*ans)


import sys

def input():
	return sys.stdin.readline().strip()

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	for _ in range(int(input())):
		(n, q) = map(int, input().split())
		p = [0] * (n + 2)
		m = [0] * (n + 2)
		k = [0] * (n + 2)
		sum = 0
		for i in range(q):
			(l, r) = map(int, input().split())
			p[l] += 1
			m[r + 1] += 1
			k[r + 1] += r - l + 1
		curr = 0
		times = 0
		for i in range(1, n + 1):
			times += p[i]
			times -= m[i]
			if m[i]:
				curr -= k[i]
			curr += times
			print(curr, end=' ')
		print('')
	return
main()


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = {}
	mp = {}
	c = 1
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		a[l] = a.get(l, []) + [c]
		a[r] = a.get(r, []) + [-c]
		c += 1
	spd = 0
	c = 0
	for i in range(n):
		r = 0
		if i in a:
			for j in a[i]:
				if j > 0:
					mp[j] = i
					c += 1
				if j < 0:
					spd -= i - mp[-j] + 1
					r += 1
		spd += c
		c -= r
		print(spd, end=' ')
	print()