The chef has cooked $n$ dishes yet again: the $i$-th dish consists of $a_i$ grams of fish and $b_i$ grams of meat.

Banquet organizers consider two dishes $i$ and $j$ equal if $a_i=a_j$ and $b_i=b_j$ at the same time.

The banquet organizers estimate the variety of $n$ dishes as follows. The variety of a set of dishes is equal to the number of different dishes in it. The less variety is, the better.

In order to reduce the variety, a taster was invited. He will eat exactly $m_i$ grams of food from each dish. For each dish, the taster determines separately how much fish and how much meat he will eat. The only condition is that he will eat exactly $m_i$ grams of the $i$-th dish in total.

Determine how much of what type of food the taster should eat from each dish so that the value of variety is the minimum possible. If there are several correct answers, you may output any of them.


-----Input-----

The first line of input data contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Each test case's description is preceded by a blank line. Next comes a line that contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of dishes. Then follows $n$ lines, $i$-th of which contains three integers $a_i$, $b_i$ and $m_i$ ($0 \leq a_i, b_i \le 10^6$; $0 \le m_i \le a_i+b_i$) — the mass of fish in $i$-th dish, the mass of meat in $i$-th dish and how many grams in total the taster should eat in $i$-th dish.

The sum of all $n$ values for all input data sets in the test does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print on the first line the minimum value of variety that can be achieved by eating exactly $m_i$ grams of food (for all $i$ from $1$ to $n$) from a dish $i$.

Then print $n$ lines that describe a way to do this: the $i$-th line should contain two integers $x_i$ and $y_i$ ($0 \leq x_i \leq a_i$; $0 \leq y_i \leq b_i$; $x_i+y_i=m_i$), where $x_i$ is how many grams of fish the taster should eat from $i$-th dish, and $y_i$ is how many grams of meat.

If there are several ways to achieve a minimum balance, print any of them.


-----Examples-----

Input
5

3
10 10 2
9 9 0
10 9 1

2
3 4 1
5 1 2

3
7 2 5
6 5 4
5 5 6

1
13 42 50

5
5 7 12
3 1 4
7 3 7
0 0 0
4 1 5
Output
1
1 1
0 0
1 0
2
0 1
1 1
2
3 2
0 4
1 5
1
8 42
2
5 7
3 1
4 3
0 0
4 1


-----Note-----

None

Difficulty: HARD
Tags: Sorting

Amortized analysis

Greedy algorithms
Skill types: Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
from collections import defaultdict
import heapq

def resolve(n, pairs):
	d = defaultdict(list)
	for (i, [a, b, m]) in enumerate(pairs):
		k = a + b - m
		(al, ar) = (a - min(a, m), a - (m - min(b, m)))
		d[k].append((al, ar, i))
	ret = [0] + [None] * n
	cnt = 0
	for (k, arr) in d.items():
		ll = []
		for (al, ar, i) in arr:
			ll.append((al, 1, i))
			ll.append((ar, -1, i))
		ll.sort(key=lambda it: (it[0], -it[1]))
		pq = []
		for (x, y, i) in ll:
			if y < 0:
				if ret[i + 1] is not None:
					continue
				cnt += 1
				while pq and pq[0][0] <= x:
					(_, j) = heapq.heappop(pq)
					ret[j + 1] = f'{pairs[j][0] - x} {pairs[j][1] - k + x}'
			else:
				heapq.heappush(pq, (x, i))
	ret[0] = str(cnt)
	return '\n'.join(ret)
t = int(input())
ans = []
for _ in range(t):
	input()
	n = int(input())
	ans.append(resolve(n, [[int(_) for _ in input().split()] for _ in range(n)]))
print('\n'.join(ans))


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]
inf = 4294967295
md = 998244353
from collections import defaultdict

def solve():
	SI()
	n = II()
	abm = LLI(n)
	stolr = defaultdict(list)
	for (i, (a, b, m)) in enumerate(abm):
		l = max(0, a - m)
		r = min(a, a + b - m)
		stolr[a + b - m].append((l, r, i))
	aa = [0] * n
	bb = [0] * n
	cnt = 0
	for lr in stolr.values():
		toa = -1
		for (l, r, i) in sorted(lr, key=lambda x: x[1]):
			(a, b, m) = abm[i]
			if l > toa:
				cnt += 1
				toa = r
			aa[i] = a - toa
			bb[i] = m - aa[i]
	print(cnt)
	for (a, b) in zip(aa, bb):
		print(a, b)
for testcase in range(II()):
	solve()


from collections import defaultdict
import sys

def solve():
	_ = sys.stdin.readline().split()
	n = int(input())
	(a, b, m) = ([], [], [])
	d = defaultdict(list)
	for i in range(n):
		(_a, _b, _m) = map(int, sys.stdin.readline().split())
		a.append(_a)
		b.append(_b)
		m.append(_m)
		d[_a + _b - _m].append(i)
	(x, y) = ([0] * n, [0] * n)
	variety = 0
	for key in d:
		lst = d[key]
		lst.sort(key=lambda i: a[i] - m[i])
		i = lst[-1]
		cur_a = max(0, a[i] - m[i])
		variety += 1
		j = len(lst) - 1
		while j >= 0:
			i = lst[j]
			if a[i] < cur_a:
				cur_a = max(0, a[i] - m[i])
				variety += 1
			x[i] = a[i] - cur_a
			y[i] = m[i] - x[i]
			j -= 1
	print(variety)
	for i in range(n):
		print(x[i], y[i])
tn = int(input())
for t in range(tn):
	solve()


for _ in range(int(input())):
	input()
	n = int(input())
	a = []
	b = []
	m = []
	for i in range(n):
		(ai, bi, mi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
		m.append(mi)
	ansa = [0] * n
	ansb = [0] * n
	events = {}
	for i in range(n):
		ma = m[i] - b[i] if m[i] > b[i] else 0
		mb = m[i] - a[i] if m[i] > a[i] else 0
		ansa[i] += ma
		ansb[i] += mb
		a[i] -= ma
		b[i] -= mb
		m[i] -= ma + mb
		diag = a[i] + b[i] - m[i]
		if diag not in events:
			events[diag] = []
		events[diag].append((a[i] - m[i], 0, i))
		events[diag].append((a[i], 1, i))
	used = [0] * n
	count = 0
	for diag in events:
		evts = sorted(events[diag])
		opened = []
		for event in evts:
			if event[1]:
				if not used[event[2]]:
					for i in opened:
						ansa[i] += a[i] - event[0]
						ansb[i] += m[i] - a[i] + event[0]
						used[i] = 1
					opened = []
					count += 1
			else:
				opened.append(event[2])
	print(count)
	for i in range(n):
		print(ansa[i], ansb[i])


import io, os
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
inf = 2147483647

def main(t):
	space = input()
	n = int(input())
	dic = {}
	target = [-1] * n
	temp = []
	for i in range(n):
		(a, b, req) = map(int, input().split())
		temp.append([a, b, req])
		if a + b - req not in dic:
			dic[a + b - req] = []
		maxa = min(a + b - req, a)
		mina = max(a - req, 0)
		dic[a + b - req].append([mina, maxa, i])
	ans = 0
	for key in dic:
		dic[key] = sorted(dic[key])
		dic[key].append([inf, inf, -1])
		heap = []
		indexlist = []
		minimum = -1
		for [front, rear, index] in dic[key]:
			if front > minimum:
				if indexlist:
					ans += 1
				while indexlist:
					target[indexlist.pop()] = minimum
				minimum = rear
				indexlist = [index]
			else:
				indexlist.append(index)
				minimum = min(minimum, rear)
	print(ans)
	for (i, ele) in enumerate(temp):
		rest = ele[0] + ele[1] - ele[2]
		print(ele[0] - target[i], ele[2] + target[i] - ele[0])
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1