Read problems statements in mandarin chinese, russian and vietnamese as well. 

Sereja has an array A consisting of n integers. Initially, all the elements of array are zero.

Sereja writes down m commands on a piece of a paper. The commands are enumerated from 1 to m. These commands can be of the following two types of commands: 
l r (1 ≤ l ≤ r ≤ n) — Increase all elements of the array by one, whose indices belongs to the range [l, r] 
l r (1 ≤ l ≤ r ≤ m) — Execute all the commands whose indices are in the range [l, r]. It's guaranteed that r is strictly less than the enumeration/number of the current command. 
Can you please help Sereja in executing all the commands written on this piece of paper.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line contains integers n and m. Next m lines contain Sereja's commands in the format, described in statement: t, l, r, where t - number of type (1 or 2).

------ Output ------ 

For each test case on different lines print an array a, after executing all the commands. The numbers have to be separated by spaces. As the numbers can be quite large, print them modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 3$
$1 ≤ n, m ≤ 10^{5}$

------ Subtasks ------ 

$Subtask #1 (20 points): 1 ≤ n, m ≤ 10 $
$Subtask #2 (30 points): 1 ≤ n, m ≤ 1000 $
$Subtask #3 (50 points): original constraints $

----- Sample Input 1 ------ 
3
5 5
1 1 2
1 4 5
2 1 2
2 1 3
2 3 4
1 2
1 1 1
1 1 1
10 10
1 1 10
2 1 1
2 1 2
2 1 3
2 1 4
2 1 5
2 1 6
2 1 7
2 1 8
2 1 9
----- Sample Output 1 ------ 
7 7 0 7 7
2
512 512 512 512 512 512 512 512 512 512

----- explanation 1 ------ 

Example case 1..
After the first command, the resulting array is [1 1 0 0 0], after second [1 1 0 1 1]. 
On third command, we repeat the 1'st and the 2'nd command, so that resulting array is [2 2 0 2 2]. 
After fourth command, the array will looks like [4 4 0 4 4]. 
Last command will apply 3'rd and 4'th commands, 
which by themselves will apply 1'st, 2'nd, 1'st, 2'nd, 3'rd(1'st, 2'nd), so resulting arrays is [7 7 0 7 7].

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
from itertools import accumulate, islice
MOD = 10 ** 9 + 7

def R():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	(n, m) = R()
	cmds = [tuple(R()) for _ in range(m)]
	da = [0] * (n + 1)
	dc = [0] * m
	d = 1
	for (i, (op, l, r)) in zip(reversed(range(m)), reversed(cmds)):
		if op == 1:
			da[l - 1] += d
			da[r] -= d
		else:
			dc[l - 1] -= d
			dc[r] += d
		d += dc[i]
	da[0] %= MOD
	print(*accumulate(islice(da, n), lambda x, y: (x + y) % MOD))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	commands = []
	for i in range(m):
		com = list(map(int, input().split()))
		commands.append(com)
	freq = [0] * m
	prefix = [0] * (n + 1)
	ini_freq = 1
	for i in range(m - 1, -1, -1):
		t = commands[i][0]
		l = commands[i][1]
		r = commands[i][2]
		ini_freq += freq[i]
		if t == 1:
			prefix[l - 1] += ini_freq
			prefix[r] -= ini_freq
		elif l == 1:
			freq[r - 1] += ini_freq
		else:
			freq[r - 1] += ini_freq
			freq[l - 2] -= ini_freq
	a = []
	p_sum = 0
	mod = 10 ** 9 + 7
	for i in range(n):
		p_sum += prefix[i]
		p_sum %= mod
		a.append(p_sum)
	print(*a)


mod = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	query = [list(map(int, input().strip().split())) for _ in range(m)]
	a = [0] * (m + 1)
	for i in range(m):
		(typ, l, r) = query[i]
		if typ == 2:
			a[l - 1] = (a[l - 1] + 1) % mod
			a[r] = (a[r] - 1) % mod
	x = 0
	for i in range(m - 1, -1, -1):
		x = (x - a[i + 1]) % mod
		(typ, l, r) = query[i]
		if typ == 2:
			a[l - 1] = (a[l - 1] + x) % mod
			a[r] = (a[r] - x) % mod
	b = [0] * (n + 1)
	x = 0
	for i in range(m):
		x = (x + a[i]) % mod
		(typ, l, r) = query[i]
		if typ == 1:
			b[l - 1] = (b[l - 1] + x + 1) % mod
			b[r] = (b[r] - x - 1) % mod
	ans = [0] * n
	x = 0
	for i in range(n):
		x = (x + b[i]) % mod
		ans[i] = x
	print(' '.join(map(str, ans)))


MOD = 1000000000.0 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ranges = [0] * (m + 1)
	sums = [0] * (m + 1)
	query = []
	for i in range(m):
		(a, b, c) = map(int, input().split())
		query.append((a, b, c))
	query = [0] + query
	t = 0
	for i in range(m, 0, -1):
		t += int(ranges[i] % MOD)
		if query[i][0] == 2:
			ranges[query[i][2]] += t + 1
			ranges[query[i][1] - 1] -= t + 1
	sums[m] = ranges[m] % MOD
	for i in range(m - 1, 0, -1):
		sums[i] = sums[i + 1] + ranges[i]
		sums[i] %= MOD
		int(sums[i])
		if sums[i] < 0:
			sums[i] += MOD
	ranges = [0] * (n + 1)
	for i in range(1, m + 1):
		if query[i][0] == 1:
			sums[i] += 1
			ranges[query[i][1]] += sums[i]
			if query[i][2] < n:
				ranges[query[i][2] + 1] -= sums[i]
	sums = [0] * (n + 1)
	for i in range(1, n + 1):
		sums[i] = sums[i - 1] + ranges[i]
		sums[i] %= MOD
		sums[i] = int(sums[i])
	print(*sums[1:])


T = int(input())
mod = 10 ** 9 + 7
for t in range(T):
	(n, m) = [int(i) for i in input().split()]
	queries = []
	diff = [0] * (n + 1)
	query1 = [0] * (m + 1)
	query1[m] = 1
	for i in range(m):
		queries.append([int(i) for i in input().split()])
	cur = 0
	for i in range(m, 0, -1):
		cur = (cur + query1[i]) % mod
		if queries[i - 1][0] == 2:
			query1[queries[i - 1][2]] += cur
			query1[queries[i - 1][1] - 1] -= cur
		else:
			diff[queries[i - 1][1] - 1] += cur
			diff[queries[i - 1][2]] -= cur
	cur = 0
	for i in range(n):
		cur = (cur + diff[i]) % mod
		print(cur, end=' ')
	print()


MOD = 10 ** 9 + 7

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v
for t in range(int(input())):
	(n, m) = map(int, input().split())
	sa = SegTree(n)
	sq = SegTree(m)
	Q = [list(map(int, input().split())) for i in range(m)]
	for i in range(m, 0, -1):
		(t, l, r) = Q[i - 1]
		c = sq.query(i) + 1
		if t == 1:
			sa.update(l, r, c)
		else:
			sq.update(l, r, c)
	a = [sa.query(i) % MOD for i in range(1, n + 1)]
	print(*a)


import numpy as np
base = 1000000000 + 7
num_cases = input()
for ii in range(0, int(num_cases)):
	(n, m) = map(int, input().split())
	A = np.zeros(n, dtype=int)
	B = np.ones([m, 4], dtype=int)
	for kk in range(0, m):
		(B[kk, 0], B[kk, 1], B[kk, 2]) = input().split()
	for kk in range(m - 1, -1, -1):
		if B[kk, 0] == 1:
			A[B[kk, 1] - 1:B[kk, 2]] += B[kk, 3] % base
		else:
			B[B[kk, 1] - 1:B[kk, 2], 3] += B[kk, 3] % base
	ll = ' '.join((str(int(x % base)) for x in A))
	print(ll)


mod = 1000000007
t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	val = []
	l = []
	r = []
	inc = []
	dec = []
	inc_v = []
	dec_v = []
	for i in range(0, max(m + 5, n + 5)):
		inc.append(0)
		dec.append(0)
		inc_v.append(0)
		dec_v.append(0)
	inc[m + 1] = 1
	val.append(0)
	l.append(0)
	r.append(0)
	for i in range(m):
		(x, y, z) = map(int, input().split())
		val.append(x)
		l.append(y)
		r.append(z)
	for i in range(m, 0, -1):
		inc[i] = dec[i] + inc[i + 1]
		if val[i] == 2:
			dec[l[i] - 1] -= inc[i]
			dec[r[i]] += inc[i]
	for i in range(1, m + 1):
		if val[i] == 1:
			inc_v[l[i]] += inc[i]
			dec_v[r[i] + 1] -= inc[i]
	ci = 0
	for i in range(1, n + 1):
		ci = ci + (inc_v[i] + dec_v[i])
		print(ci % mod, end=' ')
	print(' ')


mod = 1000000007

class SegmentTree:

	def __init__(self, n):
		self.data = [0] + [0] * (2 * n)
		self.n = n

	def query(self, idx):
		idx += self.n + 1
		a = 0
		while idx > 1:
			a += self.data[idx]
			idx //= 2
		return a

	def update(self, left, right, a):
		left += self.n
		right += self.n
		while left <= right:
			if left % 2 == 1:
				self.data[left] += a
			if right % 2 == 0:
				self.data[right] += a
			left = left + 1 >> 1
			right = right - 1 >> 1
for t in range(int(input().strip())):
	(n, m) = map(int, input().strip().split())
	sa = SegmentTree(n)
	sq = SegmentTree(m)
	q = [list(map(int, input().strip().split())) for i in range(m)]
	for i in reversed(range(m)):
		(t, l, r) = q[i]
		c = sq.query(i) + 1
		if t == 1:
			sa.update(l, r, c)
		else:
			sq.update(l, r, c)
	ans = [sa.query(i) % mod for i in range(n)]
	print(*ans)


p = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = [0] * (n + 2)
	b = [0]
	cmd = [1] * (m + 1)
	d = [0] * (m + 2)
	for i in range(1, m + 1):
		b.append([int(i) for i in input().split()])
	for i in range(m, 0, -1):
		d[i] = d[i] + d[i + 1]
		cmd[i] = cmd[i] + d[i]
		if b[i][0] == 2:
			d[b[i][2]] = d[b[i][2]] + cmd[i]
			d[b[i][1] - 1] = d[b[i][1] - 1] - cmd[i]
	for i in range(1, m + 1):
		if b[i][0] == 1:
			a[b[i][1]] = a[b[i][1]] + cmd[i]
			a[b[i][2] + 1] = a[b[i][2] + 1] - cmd[i]
	for i in range(1, n + 1):
		a[i] = (a[i] + a[i - 1]) % p
		print(a[i], end=' ')
	print()


for _ in range(int(input())):
	(n, q) = [int(i) for i in input().split()]
	l = []
	for i in range(q):
		l.append([int(i) for i in input().split()])
	subs = [0] * (q + 1)
	arr = [0] * (n + 1)
	subs[q] += 1
	ini = 0
	for i in range(q, 0, -1):
		ini += subs[i]
		ini %= 10 ** 9 + 7
		le = l[i - 1][1]
		r = l[i - 1][2]
		if l[i - 1][0] == 1:
			arr[le - 1] += ini
			arr[r] -= ini
		else:
			subs[r] += ini
			if le - 1 >= 0:
				subs[le - 1] -= ini
	m = 10 ** 9 + 7
	arr[0] = arr[0] % m
	for i in range(1, len(arr)):
		arr[i] = arr[i - 1] + arr[i]
		arr[i] = arr[i] % m
	print(*arr[:n])


T = int(input())
p = int(pow(10, 9)) + 7
for _ in range(T):
	(n, m) = (int(i) for i in input().split())
	(commands, com_count, a, d_com_count, d_a) = ([0], [0] * (m + 2), [0] * (n + 2), [0] * (m + 2), [0] * (n + 2))
	for i in range(m):
		commands.append([int(i) for i in input().split()])
	com_count[m + 1] = 1
	for i in range(m, 0, -1):
		c = commands[i]
		com_count[i] = d_com_count[i + 1] + com_count[i + 1]
		if c[0] == 2:
			d_com_count[c[2] + 1] += com_count[i]
			d_com_count[c[1]] -= com_count[i]
	for i in range(1, m + 1):
		c = commands[i]
		if c[0] == 1:
			d_a[c[1] - 1] += com_count[i]
			d_a[c[2]] -= com_count[i]
	for i in range(1, n + 1):
		a[i] = a[i - 1] + d_a[i - 1]
		print(a[i] % p, end=' ')
	print()


MOD = 10 ** 9 + 7
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	OPS = []
	for m in range(M):
		(op, l, r) = map(int, input().split())
		OPS.append((op, l, r))
	ans = [0] * (N + 2)
	acc_ans = [0] * (N + 2)
	mult = [1] * (M + 2)
	acc_mult = [0] * (M + 2)
	for i in range(M - 1, -1, -1):
		(op, l, r) = OPS[i]
		index = i + 1
		mult[index] = (acc_mult[index] + mult[index + 1] + MOD) % MOD
		if op == 2:
			acc_mult[r] += mult[index]
			acc_mult[l - 1] -= mult[index]
			acc_mult[r] %= MOD
			acc_mult[l - 1] %= MOD
		else:
			acc_ans[l] += mult[index]
			acc_ans[l] %= MOD
			acc_ans[r + 1] -= mult[index]
			acc_ans[r + 1] %= MOD
	for i in range(1, N + 1):
		acc_ans[i] += acc_ans[i - 1]
		acc_ans[i] %= MOD
	print(' '.join((str(x) for x in acc_ans[1:N + 1])))


mod = 1000000007

def push(node):
	if tree[node] == 0:
		return
	tree[node * 2] = (tree[node * 2] + tree[node]) % mod
	tree[node * 2 + 1] = (tree[node * 2 + 1] + tree[node]) % mod
	tree[node] = 0

def updateRange(node, start, end, l, r, val):
	if l <= start and end <= r:
		tree[node] = (tree[node] + val) % mod
		return
	mid = (start + end) // 2
	push(node)
	if l <= mid:
		updateRange(node * 2, start, mid, l, r, val)
	if r > mid:
		updateRange(node * 2 + 1, mid + 1, end, l, r, val)

def queryRange(node, start, end, l):
	if start == end:
		return tree[node] % mod
	push(node)
	mid = (start + end) // 2
	if l <= mid:
		return queryRange(node * 2, start, mid, l)
	else:
		return queryRange(node * 2 + 1, mid + 1, end, l)
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	temp = [0] * (n + 2)
	tree = [0] * 262150
	here = 0
	B = [[] for i in range(q + 1)]
	pq = 1
	q1 = q
	while q1 > 0:
		(a, b, c) = input().split()
		B[pq] = [int(a), int(b), int(c)]
		pq += 1
		q1 = q1 - 1
	for j in range(q, 0, -1):
		here = queryRange(1, 1, q, j)
		if B[j][0] == 2:
			updateRange(1, 1, q, B[j][1], B[j][2], here + 1)
		else:
			temp[B[j][1]] = temp[B[j][1]] + (here + 1)
			temp[B[j][2] + 1] = temp[B[j][2] + 1] - (here + 1)
	ans = 0
	for j in range(1, n + 1):
		ans = (ans + temp[j]) % mod
		print(ans, end=' ')
	print('\n')


mod = 1000000007

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def updaterange(BITTree, l, r, n, val):
	updatebit(BITTree, n, l, val)
	updatebit(BITTree, n, r + 1, -val)

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	freq = [0] * m
	ans = [0] * n
	data = []
	cnt = [1] * m
	BITTree = construct(freq, len(freq))
	for i in range(m):
		data.append(list(map(int, input().split())))
	for i in range(m - 1, -1, -1):
		x = getsum(BITTree, i)
		cnt[i] = x + 1
		if data[i][0] == 2:
			updaterange(BITTree, data[i][1] - 1, data[i][2] - 1, len(freq), x + 1)
	BITTree = construct(ans, len(ans))
	for i in range(m):
		if data[i][0] == 1:
			updaterange(BITTree, data[i][1] - 1, data[i][2] - 1, len(ans), cnt[i])
	for i in range(n):
		ans[i] = getsum(BITTree, i) % mod
		print(ans[i], end=' ')
	print()


MOD = 10 ** 9 + 7
for t in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	commands = {}
	keys = []
	for i in range(1, m + 1):
		ar = [int(x) for x in input().split()]
		commands[i] = ar
		if ar[0] == 1:
			keys.append(i)
	b = [0] * (m + 2)
	b[m] = 1
	for i in range(m - 1, -1, -1):
		b[i + 1] = b[i + 1] + b[i + 2]
		if commands[i + 1][0] == 2:
			b[commands[i + 1][2]] += b[i + 1]
			b[commands[i + 1][1] - 1] -= b[i + 1]
	ans = []
	for i in range(100005):
		ans.append(0)
	for i in range(1, m + 1):
		if commands[i][0] == 1:
			ans[commands[i][1]] = ans[commands[i][1]] + b[i]
			ans[commands[i][2] + 1] = ans[commands[i][2] + 1] - b[i]
	for i in range(1, n + 1):
		ans[i] += ans[i - 1]
		print(str(ans[i] % 1000000007), end=' ')
	print()


from itertools import accumulate
MOD = 10 ** 9 + 7

def mod_add(a, b):
	a += b
	return a if a < MOD else a - MOD

def mod_sub(a, b):
	a -= b
	return a + MOD if a < 0 else a

def R():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	(n, m) = R()
	cmds = [tuple(R()) for _ in range(m)]
	da = [0] * (n + 1)
	dc = [0] * m
	x = 1
	for (i, (op, l, r)) in zip(reversed(range(m)), reversed(cmds)):
		if op == 1:
			da[l - 1] = mod_add(da[l - 1], x)
			da[r] = mod_sub(da[r], x)
		else:
			dc[l - 1] = mod_sub(dc[l - 1], x)
			dc[r] = mod_add(dc[r], x)
		x = mod_add(x, dc[i])
	print(*accumulate(da[:-1], mod_add))


import numpy as np
mod = 1000000007
t = int(input())
while t != 0:
	(n, q) = [int(x) for x in input().split()]
	A = np.zeros(shape=(100005, 4))
	sum = 0
	Ans = 0
	answer = np.zeros(shape=n + 2)
	H = np.zeros(shape=q + 2)
	for i in range(1, q + 1):
		(ty, l, r) = [int(x) for x in input().split()]
		A[i][1] = ty
		A[i][2] = l
		A[i][3] = r
		left = int(A[i][2])
		right = int(A[i][3])
		if ty == 1:
			answer[left] = (answer[left] % mod + 1) % mod
			answer[right + 1] = (answer[right + 1] % mod - 1 + mod) % mod
		else:
			H[left - 1] = (H[left - 1] % mod - 1 + mod) % mod
			H[right] = (H[right] % mod + 1) % mod
	for i in range(q, 0, -1):
		sum = (int(sum) % mod + int(H[i]) % mod) % mod
		if sum != 0:
			left = int(A[i][2])
			right = int(A[i][3])
			if A[i][1] == 1:
				answer[left] = (answer[left] % mod + sum) % mod
				answer[right + 1] = (answer[right + 1] % mod - sum + mod) % mod
			else:
				H[left - 1] = (H[left - 1] % mod - sum + mod) % mod
				H[right] = (H[right] % mod + sum) % mod
	for rt in range(1, n + 1):
		Ans = (Ans + int(answer[rt]) % mod) % mod
		print(Ans, end=' ')
	print()
	t = t - 1


T = int(input())
i = 0
while i < T:
	(n, m) = [int(x) for x in input().split(' ')]
	q = []
	ans = []
	sumi = [0 for x in range(n + 1)]
	ans = [0 for x in range(m + 2)]
	q = [0 for x in range(m + 1)]
	for x in range(1, m + 1):
		q[x] = [int(x) for x in input().split(' ')]
	j = m
	qe = 0
	suff = [0 for x in range(m + 2)]
	while j != 0:
		if q[j][0] == 2:
			suff[j] = suff[j + 1] + ans[j]
			qe = suff[j]
			qe += 1
			ans[q[j][1] - 1] += -qe
			ans[q[j][2]] += qe
		else:
			suff[j] = suff[j + 1] + ans[j]
			ans[j] = suff[j]
			ans[j] += 1
		j -= 1
	for x in range(1, m + 1):
		if q[x][0] == 1:
			sumi[q[x][1]] += ans[x]
			if q[x][2] < n:
				sumi[q[x][2] + 1] += -ans[x]
	for x in range(1, n + 1):
		sumi[x] = (sumi[x] + sumi[x - 1]) % 1000000007
	print(' '.join((str(x) for x in sumi[1:])))
	i += 1


class soochna:
	pehla = 0
	dusra = 0
	tesra = 0

class barbar:
	shuruat = 0
	aant = 0
exam = int(input())
for i in range(exam):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	aksh = [soochna() for i in range(m + 1)]
	princy = [barbar() for i in range(m + 1)]
	veera = [barbar() for i in range(n + 1)]
	for i in range(1, n + 1):
		veera[i].shuruat = 0
		veera[i].aant = 0
	for i in range(1, m + 1):
		princy[i].shuruat = 0
		princy[i].aant = 0
	for i in range(1, m + 1):
		(s, f, j) = input().split()
		aksh[i].pehla = int(s)
		aksh[i].dusra = int(f)
		aksh[i].tesra = int(j)
	chandra = 1
	for i in range(m, 0, -1):
		chandra = chandra + princy[i].aant
		if aksh[i].pehla == 2:
			princy[aksh[i].dusra].shuruat = princy[aksh[i].dusra].shuruat + chandra
			princy[aksh[i].tesra].aant = princy[aksh[i].tesra].aant + chandra
		chandra = chandra - princy[i].shuruat
	chandra = 1
	for i in range(1, m + 1):
		chandra = chandra + princy[i].shuruat
		if aksh[i].pehla == 1:
			veera[aksh[i].dusra].shuruat = veera[aksh[i].dusra].shuruat + chandra
			veera[aksh[i].tesra].aant = veera[aksh[i].tesra].aant + chandra
		chandra = chandra - princy[i].aant
	chandra = 0
	u = 0
	for i in range(1, n + 1):
		chandra = chandra + veera[i].shuruat
		u = chandra % 1000000007
		print(u, end=' ')
		chandra = chandra - veera[i].aant
	print()


mo = 10 ** 9 + 7
for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	m = temp[1]
	a = list()
	for i in range(n):
		a.append(0)
	s = 0
	b = list()
	last = list()
	q = list()
	for i in range(m):
		b.append(0)
		last.append(0)
		q.append(list(map(int, input().split())))
	i = m - 1
	lastl = -1
	lastr = -1
	while i >= 0:
		if lastl != -1 and lastr != -1:
			last[l] = b[lastl]
			last[r + 1] = b[lastr]
		t = q[i][0]
		l = q[i][1] - 1
		r = q[i][2] - 1
		val = s + 1
		if t == 1:
			a[l] += val
			if r + 1 < n:
				a[r + 1] -= val
			s -= last[i]
			lastl = -1
			lastr = -1
		elif t == 2:
			last[l] = b[l]
			b[l] += val
			lastl = l
			if r + 1 < m:
				last[r + 1] = b[r + 1]
				b[r + 1] -= val
				lastr = r + 1
				s -= last[i]
				if lastl <= i - 1 and lastr <= i - 1:
					tooth = 2
				else:
					s += val
			elif r + 1 >= m:
				lastr = -1
		i -= 1
	s = 0
	for i in range(n):
		s += a[i]
		print(s % mo, end=' ')
	print()


class niharika:
	index = 0
	l = 0
	r = 0

class anjali:
	shrutee = 0
	lakshita = 0
papa = int(input())
while papa:
	papa = papa - 1
	(n, m) = input().split()
	m = int(m)
	n = int(n)
	a = [niharika() for i in range(m + 1)]
	c = [anjali() for i in range(m + 1)]
	v = [anjali() for i in range(n + 1)]
	for i in range(1, n + 1):
		v[i].shrutee = 0
		v[i].lakshita = 0
	for i in range(1, m + 1):
		c[i].shrutee = 0
		c[i].lakshita = 0
	for i in range(1, m + 1):
		(x, y, z) = input().split()
		a[i].index = int(x)
		a[i].l = int(y)
		a[i].r = int(z)
	sid = 1
	for i in range(m, 0, -1):
		sid = sid + c[i].lakshita
		if a[i].index == 2:
			c[a[i].l].shrutee = c[a[i].l].shrutee + sid
			c[a[i].r].lakshita = c[a[i].r].lakshita + sid
		sid = sid - c[i].shrutee
	sid = 1
	for i in range(1, m + 1):
		sid = sid + c[i].shrutee
		if a[i].index == 1:
			v[a[i].l].shrutee = v[a[i].l].shrutee + sid
			v[a[i].r].lakshita = v[a[i].r].lakshita + sid
		sid = sid - c[i].lakshita
	sid = 0
	p = 0
	tank = 1000000007
	for i in range(1, n + 1):
		sid = sid + v[i].shrutee
		p = sid % tank
		print(p, end=' ')
		sid = sid - v[i].lakshita
	print()


class sujeet:
	key = 0
	l = 0
	r = 0

class manit:
	start = 0
	end = 0
t = int(input())
while t:
	t = t - 1
	(n, m) = input().split()
	m = int(m)
	n = int(n)
	a = [sujeet() for i in range(m + 1)]
	c = [manit() for i in range(m + 1)]
	v = [manit() for i in range(n + 1)]
	for i in range(1, n + 1):
		v[i].start = 0
		v[i].end = 0
	for i in range(1, m + 1):
		c[i].start = 0
		c[i].end = 0
	for i in range(1, m + 1):
		(x, y, z) = input().split()
		a[i].key = int(x)
		a[i].l = int(y)
		a[i].r = int(z)
	sid = 1
	for i in range(m, 0, -1):
		sid = sid + c[i].end
		if a[i].key == 2:
			c[a[i].l].start = c[a[i].l].start + sid
			c[a[i].r].end = c[a[i].r].end + sid
		sid = sid - c[i].start
	sid = 1
	for i in range(1, m + 1):
		sid = sid + c[i].start
		if a[i].key == 1:
			v[a[i].l].start = v[a[i].l].start + sid
			v[a[i].r].end = v[a[i].r].end + sid
		sid = sid - c[i].end
	sid = 0
	p = 0
	for i in range(1, n + 1):
		sid = sid + v[i].start
		p = sid % 1000000007
		print(p, end=' ')
		sid = sid - v[i].end
	print()


t = input()
x = ' '
while int(t) > 0:
	(n, q) = map(int, input().split())
	A = [[0 for x in range(3)] for y in range(q + 1)]
	b = [0] * 100001
	e = [0] * 1000001
	for i in range(1, q + 1, 1):
		(A[i][0], A[i][1], A[i][2]) = map(int, input().split())
	c = 1
	for i in range(q, 0, -1):
		c = c + b[i]
		b[i] = c
		if A[i][0] == 2:
			b[A[i][1] - 1] = b[A[i][1] - 1] - c
			b[A[i][2]] = b[A[i][2]] + c
		else:
			e[A[i][1]] = e[A[i][1]] + b[i]
			e[A[i][2] + 1] = e[A[i][2] + 1] - b[i]
	d = 0
	for i in range(1, n + 1, 1):
		d = d + e[i]
		e[i] = d
		print(e[i] % 1000000007, x, end='')
	print()
	t = int(t) - 1


t = int(input())
for i in range(t):
	alte = []
	comm = []
	c = []
	a = []
	tmp = []
	sum = 0
	(n, m) = [int(i) for i in input().split(' ')]
	for j in range(0, n + 20):
		a.append(0)
	for j in range(0, m + 20):
		c.append(1)
		alte.append(0)
	tmp = [0, 0, 0]
	comm.append(tmp)
	for j in range(1, m + 1):
		tmp = [int(i) for i in input().split(' ')]
		comm.append(tmp)
	tmp = [0, 0, 0]
	comm.append(tmp)
	comm.append(tmp)
	comm.append(tmp)
	for j in range(m, 0, -1):
		alte[j] = alte[j] + sum
		sum = alte[j]
		c[j] = c[j] + alte[j]
		if comm[j][0] == 2:
			alte[comm[j][2]] += c[j]
			alte[comm[j][1] - 1] -= c[j]
	for j in range(1, m + 2):
		if comm[j][0] == 1:
			a[comm[j][1]] = a[comm[j][1]] + c[j]
			a[comm[j][2] + 1] = a[comm[j][2] + 1] - c[j]
	sum = 0
	for j in range(1, n + 2):
		a[j] += sum
		sum = a[j]
	for j in range(1, n + 1):
		print(a[j] % 1000000007, end=' ')
	print()


tc = int(input())
mod = 1000000007
for t in range(tc):
	(n, m) = map(int, input().split())
	type1 = []
	l = []
	r = []
	d = []
	ans = []
	for i in range(m + 5):
		d.append(0)
	for i in range(m):
		(x, y, z) = map(int, input().split())
		type1.append(x)
		l.append(y)
		r.append(z)
	for i in range(5):
		type1.append(0)
		l.append(0)
		r.append(0)
	for i in range(m - 1, -1, -1):
		d[i] = d[i] + d[i + 1]
		if type1[i] == 2:
			if l[i] - 2 > -1:
				d[l[i] - 2] = d[l[i] - 2] - (d[i] + 1)
			d[r[i] - 1] = d[r[i] - 1] + (d[i] + 1)
	for i in range(n + 2):
		ans.append(0)
	for i in range(m):
		if type1[i] == 1:
			ans[r[i]] = ans[r[i]] - (d[i] + 1)
			ans[l[i] - 1] = ans[l[i] - 1] + (d[i] + 1)
	for i in range(1, n):
		ans[i] = ans[i] + ans[i - 1]
	for i in range(n):
		print(ans[i] % mod, end=' ')
	print()


T = input()
space = ' '
m = 1000000007
while int(T) > 0:
	(arr_len, queries) = map(int, input().split())
	inp = [[0 for x in range(3)] for y in range(queries + 1)]
	ans = [0] * 1000001
	arr_query = [0] * 100001
	for a0 in range(1, queries + 1, 1):
		(inp[a0][0], inp[a0][1], inp[a0][2]) = map(int, input().split())
	repeat = 1
	for i in range(queries, 0, -1):
		repeat = repeat + arr_query[i]
		arr_query[i] = repeat
		if inp[i][0] == 1:
			ans[inp[i][1]] = (ans[inp[i][1]] % m + arr_query[i] % m) % m
			ans[inp[i][2] + 1] = (ans[inp[i][2] + 1] % m - arr_query[i] % m) % m
		else:
			arr_query[inp[i][2]] = (arr_query[inp[i][2]] % m + repeat % m) % m
			arr_query[inp[i][1] - 1] = (arr_query[inp[i][1] - 1] % m - repeat % m) % m
	d = 0
	for i in range(1, arr_len + 1, 1):
		d = d + ans[i]
		ans[i] = d % m
		print(ans[i] % m, space, end='')
	print()
	T = int(T) - 1


def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] = (BITTree[i] + v) % 1000000007
		if BITTree[i] < 0:
			BITTree[i] = 1000000007 + BITTree[i]
		i += i & -i

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		s %= 1000000007
		i -= i & -i
	return s

def update(BITTree, l, r, n, v):
	updatebit(BITTree, n, l, v)
	updatebit(BITTree, n, r + 1, -v)
tc = int(input())
while tc > 0:
	(n, q) = map(int, input().split())
	a = []
	b = []
	c = []
	for i in range(q):
		(a1, b1, c1) = map(int, input().split())
		a.append(a1)
		b.append(b1)
		c.append(c1)
	arr = [0] * q
	BITTree = construct(arr, q)
	update(BITTree, 0, q - 1, q, 1)
	for i in range(q - 1, -1, -1):
		if a[i] == 2:
			update(BITTree, b[i] - 1, c[i] - 1, q, getsum(BITTree, i))
	arr1 = [0] * n
	BITTree1 = construct(arr1, n)
	for i in range(q):
		if a[i] == 1:
			update(BITTree1, b[i] - 1, c[i] - 1, n, getsum(BITTree, i))
	res = []
	for i in range(n):
		x = getsum(BITTree1, i)
		res.append(x)
	print(' '.join(map(str, res)))
	tc -= 1


MOD = 1000000007

class Update:
	__slots__ = ['qtype', 'left', 'right']

	def __init__(self, qtype, left, right):
		self.qtype = qtype
		self.left = left
		self.right = right

	def execute(self, rep, nums, pos):
		if self.qtype == 1:
			nums[self.left] += 1 + rep[pos]
			if self.right + 1 < len(nums):
				nums[self.right + 1] -= 1 + rep[pos]
			return
		rep[self.right] += 1 + rep[pos]
		if self.left > 0:
			rep[self.left - 1] -= 1 + rep[pos]

def read_updates(size):
	updates = []
	for i in range(size):
		(qtype, left, right) = map(int, input().split())
		updates.append(Update(qtype, left - 1, right - 1))
	return updates

def main():
	t = int(input())
	for i in range(t):
		(n, q) = map(int, input().split())
		updates = read_updates(q)
		nums = [0 for i in range(n)]
		rep = [0 for i in range(q)]
		for j in range(q - 1, -1, -1):
			if j + 1 < q:
				rep[j] += rep[j + 1]
			updates[j].execute(rep, nums, j)
		for j in range(n):
			nums[j] %= MOD
			if j > 0:
				nums[j] += nums[j - 1]
				nums[j] %= MOD
			print(nums[j], end=' ')
		print()
main()


t = int(input())
MOD = 10 ** 9 + 7

def modulo(a, b, c):
	return (a % c + b % c) % c
while t:
	t = t - 1
	(n, m) = map(int, input().strip(' ').split(' '))
	freq = [0] * (n + 2)
	count = [0] * (m + 2)
	a = [[]] * (m + 2)
	for i in range(1, m + 1):
		a[i] = [int(x) for x in input().split(' ')]
	count[m] = 1
	count[0] = -1
	for i in range(m, 0, -1):
		count[i] += count[i + 1]
		if a[i][0] == 2:
			count[a[i][1] - 1] -= count[i]
			count[a[i][2]] += count[i]
		else:
			freq[a[i][1]] += count[i]
			freq[a[i][2] + 1] -= count[i]
	ans = []
	for i in range(1, n + 1):
		freq[i] = modulo(freq[i - 1], freq[i], MOD)
		ans.append(freq[i])
	print(*ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	ccc = []
	d = []
	k = 0
	while k <= m:
		ccc.append(0)
		k += 1
	k = 0
	while k <= n:
		arr.append(0)
		k += 1
	k = 1
	while k <= m:
		(a, b, c) = map(int, input().split())
		d.append([a, b, c])
		k += 1
	count = 0
	k = m
	while k >= 1:
		if d[k - 1][0] == 1:
			count = count + ccc[k]
			arr[d[k - 1][1] - 1] += count + 1
			arr[d[k - 1][2]] -= count + 1
		else:
			count = count + ccc[k]
			ccc[d[k - 1][1] - 1] -= count + 1
			ccc[d[k - 1][2]] += count + 1
		k -= 1
	sum = 0
	k = 0
	while k < n:
		sum += arr[k]
		print(sum % (10 ** 9 + 7), end=' ')
		k += 1
	print('')


class commands:
	query = 0
	l = 0
	r = 0

class two_query:
	first = 0
	last = 0

class one_query:
	first = 0
	last = 0
t = int(input())
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	data = [commands() for i in range(m + 1)]
	bot_top = [two_query() for i in range(m + 1)]
	top_bot = [one_query() for i in range(n + 1)]
	for i in range(1, m + 1):
		(e, f, g) = input().split()
		data[i].query = int(e)
		data[i].l = int(f)
		data[i].r = int(g)
	flag = 1
	for i in range(m, 0, -1):
		flag = flag + bot_top[i].last
		if data[i].query == 2:
			a = data[i].l
			b = data[i].r
			bot_top[a].first = bot_top[a].first + flag
			bot_top[b].last = bot_top[b].last + flag
		flag = flag - bot_top[i].first
	flag = 1
	for i in range(1, m + 1):
		flag = flag + bot_top[i].first
		if data[i].query == 1:
			a = data[i].l
			b = data[i].r
			top_bot[a].first = top_bot[a].first + flag
			top_bot[b].last = top_bot[b].last + flag
		flag = flag - bot_top[i].last
	flag = 0
	for i in range(1, n + 1):
		flag = flag + top_bot[i].first
		print(flag % 1000000007, end=' ')
		flag = flag - top_bot[i].last
	print()


def modify(tree, l, r, val, n):
	l += n
	r += n
	while l < r:
		if l & 1:
			tree[l] += val % 1000000007
			l += 1
		if r & 1:
			r -= 1
			tree[r] += val % 1000000007
		l >>= 1
		r >>= 1

def query(tree, p, n):
	res = 0
	p += n
	while p > 0:
		res += tree[p] % 1000000007
		p >>= 1
	return res

def push(tree, n):
	for i in range(1, n):
		tree[i << 1] += tree[i] % 1000000007
		tree[i << 1 | 1] += tree[i] % 1000000007
		tree[i] = 0
tc = int(input())
for test in range(tc):
	(n, m) = map(int, input().split())
	(type1, type2) = ([], [])
	tree = [0] * (2 * n)
	for _ in range(m):
		(t, l, r) = map(int, input().split())
		if t == 1:
			type1.append(list([_, l - 1, r]))
		else:
			type2.append(list([_, l - 1, r]))
	cmd = [0] * m + [1] * m
	for tty in range(len(type2) - 1, -1, -1):
		val = query(cmd, type2[tty][0], m)
		modify(cmd, type2[tty][1], type2[tty][2], val, m)
	push(cmd, m)
	for x in range(len(type1)):
		value = query(cmd, type1[x][0], m)
		modify(tree, type1[x][1], type1[x][2], value, n)
	push(tree, n)
	tree = list([x % 1000000007 for x in tree[n:]])
	print(' '.join(list(map(str, tree))))


tn = int(input().rstrip())
for ti in range(tn):
	(n, m) = map(int, input().split())
	a = [0] * n
	d = {}
	t = []
	(tl, tr) = ({}, {})
	for i in range(m):
		(ty, l, r) = map(int, input().split())
		l -= 1
		t += [[(ty, l, r), 1]]
		if ty == 1:
			d[l] = d.get(l, []) + [i]
			d[r] = d.get(r, []) + [i]
		else:
			tl[l] = tl.get(l, []) + [i]
			tr[r] = tr.get(r, []) + [i]
	activ = {}
	s = 1
	for i in range(m - 1, -1, -1):
		(ty, l, r) = t[i][0]
		t[i][1] = s
		if activ:
			for j in tl.get(i, ()):
				del activ[j]
				s -= t[j][1]
		for j in tr.get(i, ()):
			activ[j] = True
			s += t[j][1]
	activ = {}
	s = 0
	l = -1
	for r in sorted(d.keys()):
		activ_b = bool(activ)
		s_temp = 0
		for i in d[r]:
			if activ.get(i, False):
				del activ[i]
				s_temp -= t[i][1]
			else:
				activ[i] = True
				s_temp += t[i][1]
		if activ_b:
			for k in range(l, r):
				a[k] = s % (10 ** 9 + 7)
		l = r
		s += s_temp
	print(' '.join(map(str, a)))


tn = int(input().rstrip())
for ti in range(tn):
	(n, m) = map(int, input().split())
	a = [0] * n
	dk = []
	(dl, dr) = ({}, {})
	t = []
	(tl, tr) = ({}, {})
	for i in range(m):
		(ty, l, r) = map(int, input().split())
		l -= 1
		t += [[(ty, l, r), 1]]
		if ty == 1:
			dk += [l, r]
			dl[l] = dl.get(l, []) + [i]
			dr[r] = dr.get(r, []) + [i]
		else:
			tl[l] = tl.get(l, []) + [i]
			tr[r] = tr.get(r, []) + [i]
	activ = {}
	s = 1
	for i in range(m - 1, -1, -1):
		(ty, l, r) = t[i][0]
		t[i][1] = s
		if activ:
			for j in tl.get(i, ()):
				del activ[j]
				s -= t[j][1]
		for j in tr.get(i, ()):
			activ[j] = True
			s += t[j][1]
	activ = {}
	s = 0
	last = -1
	for j in sorted(dk):
		if j == last:
			continue
		if activ:
			for k in range(last, j):
				a[k] = s % (10 ** 9 + 7)
			for i in dr.get(j, ()):
				del activ[i]
				s -= t[i][1]
		for i in dl.get(j, ()):
			activ[i] = True
			s += t[i][1]
		last = j
	print(' '.join(map(str, a)))


from sys import stdin
from itertools import accumulate

def nextpower(x):
	count = 0
	while x > 0:
		count += 1
		x >>= 1
	return 1 << count

def construct_tree(ar, seg, low, high, pos):
	if low == high:
		seg[pos] = count[low]
		return
	mid = (low + high) // 2
	construct_tree(ar, seg, low, mid, 2 * pos + 1)
	construct_tree(ar, seg, mid + 1, high, 2 * pos + 2)
	seg[pos] = 0

def traverse(seg, node, low, high, pos):
	if low == high and low == node:
		return seg[pos]
	mid = (low + high) // 2
	if seg[pos] != 0:
		seg[2 * pos + 1] += seg[pos]
		seg[2 * pos + 2] += seg[pos]
		seg[pos] = 0
	if node > mid:
		return traverse(seg, node, mid + 1, high, 2 * pos + 2)
	else:
		return traverse(seg, node, low, mid, 2 * pos + 1)

def count_query(seg, qlow, qhigh, low, high, pos, val):
	if qlow <= low and qhigh >= high:
		seg[pos] += val
		return
	if qlow > high or qhigh < low:
		return
	mid = (low + high) // 2
	seg[2 * pos + 1] += seg[pos]
	seg[2 * pos + 2] += seg[pos]
	seg[pos] = 0
	count_query(seg, qlow, qhigh, low, mid, 2 * pos + 1, val)
	count_query(seg, qlow, qhigh, mid + 1, high, 2 * pos + 2, val)
mod = 10 ** 9 + 7
T = int(stdin.readline())
while T:
	T -= 1
	(n, m) = map(int, stdin.readline().split())
	a = []
	for i in range(m):
		a.append(tuple(map(int, stdin.readline().split())))
	count = [1] * m
	if m & m - 1 == 0:
		seg = [0] * (2 * m - 1)
	else:
		seg = [0] * (2 * nextpower(m) - 1)
	construct_tree(count, seg, 0, m - 1, 0)
	for (index, query) in enumerate(reversed(a)):
		count[m - index - 1] = traverse(seg, m - index - 1, 0, m - 1, 0)
		if query[0] == 2:
			count_query(seg, query[1] - 1, query[2] - 1, 0, m - 1, 0, count[m - index - 1])
	ans = [0] * (n + 1)
	for (index, query) in enumerate(a):
		if query[0] == 1:
			ans[query[1] - 1] += count[index]
			ans[query[2]] -= count[index]
	ans = list(accumulate(ans))[:-1]
	for i in ans:
		print(i % mod, end=' ')
	print()


mod = 1000000007

def gsum(bit, i):
	sum = 0
	while i > 0:
		sum += bit[i]
		i -= i & -i
	return sum

def take_input(q, m):
	for _ in range(m):
		(type, x, y) = map(int, input().split())
		q.append([type, [x, y]])

def solve(q, m, v):
	for z in range(m, 0, -1):
		x = q[z][1][1]
		type = q[z][0]
		y = q[z][1][0]
		if type == 2:
			lala = gsum(bit, z)
			f(bit, y, x, lala)
		else:
			lala = gsum(bit, z)
			v[y] += lala
			v[x + 1] -= lala

def f(bit, y, x, val):
	ubit(bit, m, y, val)
	ubit(bit, m, x + 1, -val)

def print_ans(ans):
	print(*ans)

def ubit(bit, n, i, val):
	while i <= n:
		bit[i] += val
		i += i & -i
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	bit = [0] * (m + 5)
	v = [0] * (n + 5)
	q = [0]
	ubit(bit, m, 1, 1)
	take_input(q, m)
	solve(q, m, v)
	ans = []
	for i in range(1, n + 1):
		v[i] = (v[i] + v[i - 1]) % mod
		ans.append(v[i])
	print_ans(ans)


t = int(input())
mod = 1000000007
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	q = []
	ctr = []
	dp = []
	for i in range(m):
		ctr.append(1)
		dp.append(0)
	for i in range(m):
		(type, l, r) = [int(x) for x in input().split()]
		q.append([type, l, r])
	i = m - 1
	if q[i][0] == 2:
		dp[q[i][2] - 1] += ctr[i]
		if q[i][1] - 2 >= 0:
			dp[q[i][1] - 2] -= ctr[i]
	for i in range(m - 2, -1, -1):
		dp[i] += dp[i + 1]
		ctr[i] += dp[i]
		if q[i][0] == 2:
			dp[q[i][2] - 1] += ctr[i]
			if q[i][1] - 2 >= 0:
				dp[q[i][1] - 2] -= ctr[i]
	dp = []
	for i in range(n):
		dp.append(0)
	for i in range(m):
		if q[i][0] == 1:
			dp[q[i][1] - 1] += ctr[i]
			if q[i][2] < n:
				dp[q[i][2]] -= ctr[i]
	print(dp[0] % mod, end=' ')
	for i in range(1, n):
		dp[i] += dp[i - 1]
		print(dp[i] % mod, end=' ')
	print('')


class data:
	key = 0
	l = 0
	r = 0

class rep:
	start = 0
	end = 0
test = int(input())
for i in range(test):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	arr = [data() for i in range(m + 1)]
	comp = [rep() for i in range(m + 1)]
	val = [rep() for i in range(n + 1)]
	for i in range(1, n + 1):
		val[i].start = 0
		val[i].end = 0
	for i in range(1, m + 1):
		comp[i].start = 0
		comp[i].end = 0
	for i in range(1, m + 1):
		(x, y, z) = input().split()
		arr[i].key = int(x)
		arr[i].l = int(y)
		arr[i].r = int(z)
	temp = 1
	for i in range(m, 0, -1):
		temp = temp + comp[i].end
		if arr[i].key == 2:
			comp[arr[i].l].start = comp[arr[i].l].start + temp
			comp[arr[i].r].end = comp[arr[i].r].end + temp
		temp = temp - comp[i].start
	temp = 1
	for i in range(1, m + 1):
		temp = temp + comp[i].start
		if arr[i].key == 1:
			val[arr[i].l].start = val[arr[i].l].start + temp
			val[arr[i].r].end = val[arr[i].r].end + temp
		temp = temp - comp[i].end
	temp = 0
	for i in range(1, n + 1):
		temp = temp + val[i].start
		ans = temp % 1000000007
		print(ans, end=' ')
		temp = temp - val[i].end
	print()


mod = 10 ** 9 + 7
t = int(input())
td = dict()
for _ in range(t):
	(n, m) = map(int, input().split())
	queries = []
	ass = [0] * (n + 1)
	for i in range(m):
		(a, b, c) = map(int, input().split())
		queries.append((a, b, c))
		if a == 1:
			ass[b - 1] += 1
			ass[c] -= 1
	queries = queries[::-1]
	stk = [0] * (2 * m)
	stc = 0
	for q in range(m):
		(a, b, c) = (queries[q][0], queries[q][1], queries[q][2])
		if a == 1:
			ass[b - 1] += stc + stk[q]
			ass[c] -= stc + stk[q]
		else:
			stk[m - c] += stk[q] + 1 + stc
			stk[m - b + 1] -= stk[q] + 1 + stc
		stc += stk[q]
	arr = [0] * n
	l = 0
	for i in range(n):
		l += ass[i]
		if l > 0:
			arr[i] = l % mod
	print(*arr)


t = int(input())
ans = []
for i in range(t):
	(n, m) = list(map(int, input().split()))
	commands = []
	for j in range(m):
		(t, l, r) = list(map(int, input().split()))
		commands.append((t, l, r))
	actual_repetition_count = [0 for j in range(m)]
	pseudo_repetition_count = [0 for j in range(m)]
	for j in range(m - 1, -1, -1):
		(t, l, r) = commands[j]
		l -= 1
		r -= 1
		if j < m - 1:
			pseudo_repetition_count[j] += pseudo_repetition_count[j + 1]
		if t == 2:
			actual_repetition_count[j] += pseudo_repetition_count[j] + 1
			inc = actual_repetition_count[j]
			pseudo_repetition_count[r] += inc
			if l > 0:
				pseudo_repetition_count[l - 1] -= inc
		else:
			actual_repetition_count[j] += pseudo_repetition_count[j] + 1
	final_list = [0 for j in range(n)]
	for j in range(m):
		(t, l, r) = commands[j]
		l -= 1
		r -= 1
		if t == 1:
			inc = actual_repetition_count[j]
			final_list[l] += inc
			if r < n - 1:
				final_list[r + 1] -= inc
	for j in range(1, n):
		final_list[j] += final_list[j - 1]
	for j in range(0, n):
		final_list[j] = final_list[j] % 1000000007
	ans.append(final_list)
for x in ans:
	for (idx, ele) in enumerate(x):
		if idx < len(x) - 1:
			print(str(ele) + ' ', end='')
		else:
			print(str(ele) + '\n', end='')


for tcc in range(int(input())):
	(n, m) = map(int, input().split())
	start = [0 for i in range(m + 1)]
	end = [0 for i in range(m + 1)]
	freq = [1 for i in range(m + 1)]
	cmdlist = []
	newcmdlist = {}
	for mit in range(m):
		cmdlist.append(input())
	co = 0
	for index in range(m):
		lcmd = cmdlist.pop()
		(t, l, r) = map(int, lcmd.split())
		zz = m - index
		co = co + start[zz]
		freq[zz] = freq[zz] + co
		if t == 2:
			start[r] = start[r] + freq[zz]
			end[l] = end[l] + freq[zz]
		else:
			newcmdlist[m - index] = lcmd
		co = co - end[zz]
	start = [0 for i in range(n + 1)]
	end = [0 for i in range(n + 1)]
	val = [0 for i in range(n + 1)]
	co = 0
	for i in range(1, m + 1):
		if i in newcmdlist:
			(t, l, r) = map(int, newcmdlist[i].split())
			start[l] = start[l] + freq[i]
			end[r] = end[r] + freq[i]
	for i in range(1, n + 1):
		co = co + start[i]
		val[i] = co
		co = co - end[i]
		print(val[i] % 1000000007, end=' ')
	print()


class data:
	key = 0
	l = 0
	r = 0

class repete:
	start = 0
	end = 0
test = int(input())
for i in range(test):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	arr = [data() for i in range(m + 1)]
	com = [repete() for i in range(m + 1)]
	val = [repete() for i in range(n + 1)]
	for i in range(1, n + 1):
		val[i].start = 0
		val[i].end = 0
	for i in range(1, m + 1):
		com[i].start = 0
		com[i].end = 0
	for i in range(1, m + 1):
		(x, y, z) = input().split()
		arr[i].key = int(x)
		arr[i].l = int(y)
		arr[i].r = int(z)
	temp = 1
	for i in range(m, 0, -1):
		temp = temp + com[i].end
		if arr[i].key == 2:
			com[arr[i].l].start = com[arr[i].l].start + temp
			com[arr[i].r].end = com[arr[i].r].end + temp
		temp = temp - com[i].start
	temp = 1
	for i in range(1, m + 1):
		temp = temp + com[i].start
		if arr[i].key == 1:
			val[arr[i].l].start = val[arr[i].l].start + temp
			val[arr[i].r].end = val[arr[i].r].end + temp
		temp = temp - com[i].end
	temp = 0
	p = 0
	for i in range(1, n + 1):
		temp = temp + val[i].start
		p = temp % 1000000007
		print(p, end=' ')
		temp = temp - val[i].end
	print()


T = int(input().strip())
while T > 0:
	T -= 1
	(N, M) = list(map(int, input().strip().split()))
	commands = [None]
	incur = [0] * (M + 2)
	ans = [0] * (N + 2)
	for i in range(1, M + 1):
		commands.append(list(map(int, input().strip().split())))
	inc = 0
	for i in range(M, 0, -1):
		if commands[i][0] == 1:
			ans[commands[i][1]] += inc + 1
			ans[commands[i][2] + 1] -= inc + 1
			inc -= incur[i]
		else:
			inc += 1
			prev_incur = incur[i]
			incur[commands[i][1]] += inc
			incur[commands[i][2] + 1] -= inc
			tc = 0
			if commands[i][1] <= i - 1:
				tc += inc
			if commands[i][2] + 1 <= i - 1:
				tc -= inc
			inc += tc - prev_incur - 1
	res = [ans[1]]
	for i in range(2, N + 2):
		res.append(res[-1] + ans[i])
	print(' '.join((str(res[i] % (10 ** 9 + 7)) for i in range(N))))


from collections import defaultdict

def printResult(result, n):
	current = 0
	for i in range(n):
		current += result[i]
		current %= 10 ** 9 + 7
		print(current, end=' ')
	print()
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	result = defaultdict(int)
	repeats = defaultdict(int)
	queries = []
	current_query = m
	repeat = 0
	for i in range(m):
		queries.append(list(map(int, input().split())))
	for (t, l, r) in reversed(queries):
		current_query -= 1
		repeat += repeats[current_query]
		if t == 2:
			repeats[r - 1] += repeat + 1
			repeats[l - 2] -= repeat + 1
		else:
			result[l - 1] += repeat + 1
			result[r] -= repeat + 1
	printResult(result, n)


T = int(input().strip())
for _ in range(T):
	(n, m) = input().strip().split(' ')
	(n, m) = [int(n), int(m)]
	com = [0] * (m + 1)
	for y in range(1, m + 1):
		(t, l, r) = input().strip().split(' ')
		(t, l, r) = [int(t), int(l), int(r)]
		com[y] = [t, l, r]
	a = [1] * (m + 1)
	b = [0] * (m + 1)
	for i in range(m, 0, -1):
		if i <= m - 1:
			b[i] = b[i] + b[i + 1]
		if com[i][0] == 2:
			b[com[i][2]] += b[i] + 1
			if com[i][1] - 1 >= 1:
				b[com[i][1] - 1] -= b[i] + 1
	summ = [0] * (n + 1)
	for i in range(1, m + 1):
		if com[i][0] == 1:
			summ[com[i][1]] = summ[com[i][1]] + (b[i] + 1)
			if com[i][2] + 1 <= n:
				summ[com[i][2] + 1] = summ[com[i][2] + 1] - (b[i] + 1)
	print(summ[1] % 1000000007, end=' ')
	for i in range(2, n + 1):
		summ[i] = (summ[i] % 1000000007 + summ[i - 1] % 1000000007) % 1000000007
		print(summ[i] % 1000000007, end=' ')
	print()


t = input()
while int(t) > 0:
	k = 1
	l = 0
	(n, q) = map(int, input().split())
	t1 = [[0 for x in range(3)] for y in range(q + 1)]
	t2 = [0] * 100001
	t3 = [0] * 1000001
	for i in range(1, q + 1, 1):
		(t1[i][0], t1[i][1], t1[i][2]) = map(int, input().split())
	for i in range(q, 0, -1):
		k = k + t2[i]
		t2[i] = k
		if t1[i][0] == 1:
			t3[t1[i][2] + 1] = t3[t1[i][2] + 1] - t2[i]
			t3[t1[i][1]] = t3[t1[i][1]] + t2[i]
		else:
			t2[t1[i][2]] = t2[t1[i][2]] + k
			t2[t1[i][1] - 1] = t2[t1[i][1] - 1] - k
	for i in range(1, n + 1, 1):
		l = l + t3[i]
		t3[i] = l
		print(t3[i] % 1000000007, '', end='')
	print()
	t = int(t) - 1


t = input()
x = ' '
while int(t) > 0:
	k = 1
	l = 0
	(n, q) = map(int, input().split())
	a = [[0 for x in range(3)] for y in range(q + 1)]
	B = [0] * 100001
	c = [0] * 1000001
	for i in range(1, q + 1, 1):
		(a[i][0], a[i][1], a[i][2]) = map(int, input().split())
	for i in range(q, 0, -1):
		k = k + B[i]
		B[i] = k
		if a[i][0] == 1:
			c[a[i][2] + 1] = c[a[i][2] + 1] - B[i]
			c[a[i][1]] = c[a[i][1]] + B[i]
		else:
			B[a[i][2]] = B[a[i][2]] + k
			B[a[i][1] - 1] = B[a[i][1] - 1] - k
	for i in range(1, n + 1, 1):
		l = l + c[i]
		c[i] = l
		print(c[i] % 1000000007, x, end='')
	print()
	t = int(t) - 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	p = []
	for j in range(m):
		l = list(map(int, input().split()))
		p.append(l)
	q = [0] * m
	q[0] = 1
	d = []
	r = 1
	for k in range(m - 1, -1, -1):
		if p[k][0] == 2:
			a = p[k][1]
			b = p[k][2]
			q[a - 1] = q[a - 1] + r
			q[b] = q[b] - r
		else:
			d.append(k)
		r = r - q[k]
	for j in range(1, m):
		q[j] = q[j] + q[j - 1]
	s = [0] * n
	for h in d:
		a = p[h][1]
		b = p[h][2]
		s[a - 1] = s[a - 1] + q[h]
		if b != n:
			s[b] = s[b] - q[h]
	print(s[0] % 1000000007, end=' ')
	for l in range(1, n):
		s[l] = s[l] + s[l - 1]
		print(s[l] % 1000000007, end=' ')
	print()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	finalarr = [0] * n
	command = []
	times = [0] * (m + 1)
	times[m] = 1
	times[0] = -1
	for j in range(m):
		l = list(map(int, input().split()))
		command.append(l)
	s = 0
	for j in range(m, -1, -1):
		if j - 1 >= 0:
			initial = command[j - 1][1]
			final = command[j - 1][2]
		s = s + times[j]
		times[j] = s
		if j - 1 >= 0 and command[j - 1][0] == 2:
			if initial - 1 >= 0:
				times[initial - 1] = times[initial - 1] - s
			times[final] = times[final] + s
	times = times[1:]
	s = 0
	for j in range(m - 1, -1, -1):
		initial = command[j][1] - 1
		final = command[j][2] - 1
		if command[j][0] == 1:
			finalarr[initial] = finalarr[initial] + times[j]
			if final + 1 < n:
				finalarr[final + 1] = finalarr[final + 1] - times[j]
	S = ''
	s = 0
	for j in range(n):
		s = (s + finalarr[j]) % 1000000007
		S = S + str(s) + ' '
	print(S)


def getsum(BITTree, i):
	s = 0
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	while i <= n:
		BITTree[i] += v
		i += i & -i

def fun(BITTree, a, b, v):
	updatebit(BITTree, m, a, v)
	updatebit(BITTree, m, b + 1, -v)
t = int(input())
for x in range(t):
	(n, m) = map(int, input().split())
	BITTree = [0] * (m + 10)
	v = [0] * (n + 5)
	updatebit(BITTree, m, 1, 1)
	q = [0]
	for z in range(m):
		(ty, a, b) = map(int, input().split())
		q.append([ty, [a, b]])
	for z in range(m, 0, -1):
		ty = q[z][0]
		a = q[z][1][0]
		b = q[z][1][1]
		if ty == 1:
			inc = getsum(BITTree, z)
			v[a] += inc
			v[b + 1] -= inc
		else:
			inc = getsum(BITTree, z)
			fun(BITTree, a, b, inc)
	ans = []
	for i in range(1, n + 1):
		v[i] = v[i] + v[i - 1]
		v[i] = v[i] % 1000000007
		ans.append(v[i])
	print(*ans)


class BIT(object):

	def __init__(self, arr):
		self.arr = [0] * (len(arr) + 1)

	def update(self, idx, val):
		idx += 1
		while idx < len(self.arr):
			self.arr[idx] = self.arr[idx] + val
			idx += idx & -idx

	def update_(self, l, r, val):
		self.update(l, val)
		self.update(r + 1, -val)

	def prefixQuery(self, end):
		res = 0
		end += 1
		while end > 0:
			res = (self.arr[end] + res) % 1000000007
			end -= end & -end
		return res % 1000000007

	def rangeQuery(self, from_, to):
		return self.prefixQuery(to) - self.prefixQuery(from_ - 1)

def solve(qs, n):
	a = [0 for i in range(n)]
	f = [1 for i in range(len(qs))]
	queries = BIT(f)
	array = BIT(a)
	i = len(qs) - 1
	for (t, l, r) in reversed(qs):
		if t == 2:
			num = queries.prefixQuery(i)
			f[i] = (f[i] + num) % 1000000007
			queries.update_(l - 1, r - 1, f[i])
		else:
			num = queries.prefixQuery(i)
			array.update_(l - 1, r - 1, num + f[i])
		i -= 1
	for i in range(n):
		num = array.prefixQuery(i)
		print(num, end=' ')
	print()
from sys import stdin, stdout
for _ in range(int(stdin.readline().strip())):
	(n, m) = map(int, stdin.readline().strip().split())
	qs = []
	while m:
		(t, l, r) = map(int, stdin.readline().strip().split())
		qs.append((t, l, r))
		m -= 1
	solve(qs, n)


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	calls = [0 for i in range(q)]
	prefixsum = [0 for i in range(n)]
	queries = []
	curr = 0
	for i in range(q):
		(m, l, r) = map(int, input().split())
		l -= 1
		r -= 1
		queries.append((m, l, r))
	for i in range(q - 1, -1, -1):
		(tempm, templ, tempr) = (queries[i][0], queries[i][1], queries[i][2])
		curr += calls[i]
		if tempm == 2:
			calls[tempr] += curr + 1
			if templ > 0:
				calls[templ - 1] -= curr + 1
		else:
			prefixsum[templ] += curr + 1
			if tempr < n - 1:
				prefixsum[tempr + 1] -= curr + 1
	answer = []
	temp = 0
	for i in prefixsum:
		temp += i
		answer.append(temp % mod)
	print(*answer)


t = int(input().strip())
for a0 in range(t):
	(n, m) = [int(_) for _ in input().strip().split()]
	a = [0] * n
	l1 = []
	for b0 in range(m):
		(e, p, q) = [int(_) for _ in input().strip().split()]
		l1.append([e, p, q])
	l2 = l1
	step = [0] * m
	y = 1
	l2.reverse()
	for i in range(m):
		y += step[i]
		if l2[i][0] == 1:
			a[l2[i][1] - 1] += y
			if l2[i][2] < n:
				a[l2[i][2]] -= y
		else:
			step[m - l2[i][2]] += y
			if m - l2[i][1] + 1 < m:
				step[m - l2[i][1] + 1] -= y
	x = 0
	for i in range(n - 1):
		x += a[i]
		x = x % 1000000007
		print(x, end=' ')
	print((x + a[n - 1]) % 1000000007)


def main():
	T = int(input())
	for t in range(T):
		li = list(map(int, input().strip().split()))
		n = li[0]
		m = li[1]
		arr = []
		for i in range(n):
			arr.append(0)
		quer = []
		for i in range(m):
			(t, l, r) = map(int, input().strip().split())
			quer.append([t, l - 1, r - 1, []])
		ans = 1
		for i in range(m - 1, -1, -1):
			for j in range(len(quer[i][3])):
				ans += quer[i][3][j][0] * quer[i][3][j][1]
			if quer[i][0] == 1:
				arr[quer[i][1]] += ans
				if quer[i][2] + 1 < n:
					arr[quer[i][2] + 1] -= ans
			else:
				if quer[i][1] - 1 >= 0:
					quer[quer[i][1] - 1][3].append([-1, ans])
				quer[quer[i][2]][3].append([1, ans])
		sumer = 0
		for i in range(n):
			sumer += arr[i]
			print(sumer % (10 ** 9 + 7), end=' ')
		print('')
main()


T = int(input())
for x in range(T):
	[n, m] = [int(y) for y in input().split()]
	l1 = []
	A = []
	l2 = []
	for j in range(n):
		A.append(0)
	for j in range(m):
		l1.append([int(y) for y in input().split()])
		l1[j].append([])
	ans = 1
	for j in range(m - 1, -1, -1):
		for k in range(len(l1[j][3])):
			ans += l1[j][3][k][0] * l1[j][3][k][1]
		if l1[j][0] == 2:
			if l1[j][1] - 2 >= 0:
				l1[l1[j][1] - 2][3].append([-1, ans])
			l1[l1[j][2] - 1][3].append([1, ans])
		else:
			A[l1[j][1] - 1] += ans
			if l1[j][2] < len(A):
				A[l1[j][2]] -= ans
	s = 0
	for j in range(n):
		s += A[j]
		print(s % (7 + 10 ** 9), end=' ')
	print()


from sys import stdin
input = stdin.readline
M = 1000000007

def update1(x, y):
	while x <= n:
		power[x] = power[x] + y
		x += x & -x

def update2(x, y):
	while x <= m:
		query[x] = query[x] + y
		x += x & -x
for t in range(int(input())):
	(n, m) = map(int, input().split())
	queries = [0]
	size = max(m, n) + 1
	(power, query) = ([0] * size, [0] * size)
	for tc in range(1, m + 1):
		queries.append(list(map(int, input().split())))
		update2(tc, 1)
		update2(tc + 1, -1)
	for i in range(m, 0, -1):
		(p, x) = (0, i)
		while x:
			p = p + query[x]
			x -= x & -x
		if queries[i][0] == 1:
			update1(queries[i][1], p)
			update1(queries[i][2] + 1, -p)
		else:
			update2(queries[i][1], p)
			update2(queries[i][2] + 1, -p)

	def ans(x):
		a = 0
		while x:
			a = a + power[x]
			x -= x & -x
		return a % M
	print(' '.join(map(str, map(lambda x: ans(x), range(1, n + 1)))))


import numpy as np
t = int(input())
while t:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	arr = np.zeros(n + 2, dtype='object')
	tasks = np.zeros((m + 1, 4), dtype='object')
	i = 1
	while i <= m:
		(task_type, left, right) = input().split()
		task_type = int(task_type)
		left = int(left)
		right = int(right)
		tasks[i] = [task_type, left, right, 1]
		i += 1
	inc = np.zeros(m + 1, dtype='object')
	i = m
	inc_curr = 0
	while i > 0:
		if tasks[i, 0] == 2:
			inc_curr += inc[i]
			tasks[i, 3] = 1 + inc_curr
			inc[tasks[i, 2]] += tasks[i, 3]
			inc[tasks[i, 1] - 1] -= tasks[i, 3]
		else:
			inc_curr += inc[i]
			tasks[i, 3] = 1 + inc_curr
			arr[tasks[i, 1]] += tasks[i, 3]
			arr[tasks[i, 2] + 1] -= tasks[i, 3]
		i -= 1
	curr = 0
	i = 1
	print()
	while i <= n:
		curr = (curr + arr[i]) % 1000000007
		print(curr, end=' ')
		i += 1
	t -= 1


class obj:

	def __init__(self, val):
		self.value = val

def func():
	a = input().split()
	n = int(a[0])
	m = int(a[1])
	g_data = []
	list2 = []
	list1 = []
	data = [0 for i in range(n + 1)]
	freq = [0 for i in range(m)]
	temp = [[] for i in range(m)]
	obarr = [obj(1) for i in range(m)]
	mod = 1000000007
	for f in range(m):
		a = input().split()
		i = int(a[0])
		j = int(a[1])
		k = int(a[2])
		g_data.append([j - 1, k - 1])
		if i == 2:
			list2.append(f)
		elif i == 1:
			list1.append(f)
			freq[f] = 1
	for i in reversed(list2):
		start = g_data[i][0]
		end = g_data[i][1]
		if start != 0:
			temp[start - 1].append([-1, obarr[i]])
		temp[end].append([1, obarr[i]])
	ans = 0
	for i in range(temp.__len__() - 1, -1, -1):
		for j in temp[i]:
			ans += j[0] * j[1].value
		obarr[i].value += ans
		freq[i] += ans
	for i in list1:
		start = g_data[i][0]
		end = g_data[i][1]
		val = freq[i]
		data[start] += val
		data[start] %= mod
		data[end + 1] -= val
	ans = 0
	for i in data[0:-1]:
		ans += i
		ans %= mod
		print(ans, end=' ')
t = int(input())
for i in range(t):
	func()
	print('')


class obj:

	def __init__(self, val):
		self.value = val

	def __repr__(self):
		return str(self.value)

def func():
	a = input().split()
	n = int(a[0])
	m = int(a[1])
	g_data = []
	list2 = []
	list1 = []
	data = [0 for i in range(n + 1)]
	freq = [0 for i in range(m)]
	temp = [[] for i in range(m)]
	obarr = [obj(1) for i in range(m)]
	mod = 1000000007
	for f in range(m):
		a = input().split()
		i = int(a[0])
		j = int(a[1])
		k = int(a[2])
		g_data.append([j - 1, k - 1])
		if i == 2:
			list2.append(f)
		elif i == 1:
			list1.append(f)
			freq[f] = 1
	for i in reversed(list2):
		start = g_data[i][0]
		end = g_data[i][1]
		if start != 0:
			temp[start - 1].append([-1, obarr[i]])
		temp[end].append([1, obarr[i]])
	ans = 0
	for i in range(temp.__len__() - 1, -1, -1):
		for j in temp[i]:
			ans += j[0] * j[1].value
		obarr[i].value += ans
		freq[i] += ans
	for i in list1:
		start = g_data[i][0]
		end = g_data[i][1]
		val = freq[i]
		data[start] += val
		data[start] %= mod
		data[end + 1] -= val
	ans = 0
	for i in data[0:-1]:
		ans += i
		ans %= mod
		print(ans, end=' ')
t = int(input())
for i in range(t):
	func()
	print('')

def binary(l, key, opt):
	left = 0
	right = l.__len__()
	while left < right:
		mid = (left + right) // 2
		if l[mid] > key:
			right = mid - 1
		elif l[mid] == key:
			return mid
		else:
			left = mid + 1
	if opt == 1:
		return mid + 1
	else:
		return mid - 1


for _ in range(int(input())):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	Ar = [[0]] * (m + 1)
	for i in range(1, m + 1):
		Ar[i] = list(map(int, input().split()))
	A = [0] * (n + 2)
	B = [0] * (m + 2)
	sm = 0
	for i in range(m, 0, -1):
		sm = sm + B[i]
		if Ar[i][0] == 2:
			B[Ar[i][2]] += sm + 1
			B[Ar[i][1] - 1] -= sm + 1
		else:
			A[Ar[i][1]] += sm + 1
			A[Ar[i][2] + 1] -= sm + 1
	sm = 0
	for i in range(1, n + 1):
		sm += A[i]
		print(sm % 1000000007, end=' ')
	print()


t = int(input())
while t > 0:
	(n, m) = map(int, input().split(' '))
	a = []
	q0 = [0]
	q1 = [0]
	q2 = [0]
	q3 = [0]
	for i in range(1, m + 1):
		(x, y, z) = map(int, input().split(' '))
		q0.append(x)
		q1.append(y)
		q2.append(z)
		q3.append(0)
	if q0[m] == 2:
		q3[q2[m]] += q3[m] + 1
		q3[q1[m] - 1] -= q3[m] + 1
	for i in range(2, m + 1):
		q3[-i] += q3[-(i - 1)]
		if q0[-i] == 2:
			q3[q1[-i] - 1] -= q3[-i] + 1
			q3[q2[-i]] += q3[-i] + 1
	for i in range(1, n + 3):
		a.append(0)
	for i in range(1, m + 1):
		if q0[i] == 1:
			a[q1[i]] += q3[i] + 1
			a[q2[i] + 1] -= q3[i] + 1
	for i in range(1, n + 1):
		a[i] += a[i - 1]
	for i in range(1, n + 1):
		a[i] %= 1000000007
	for i in range(1, n + 1):
		print(a[i], end=' ')
	print()
	t -= 1