A known chef has prepared $n$ dishes: the $i$-th dish consists of $a_i$ grams of fish and $b_i$ grams of meat.

The banquet organizers estimate the balance of $n$ dishes as follows. The balance is equal to the absolute value of the difference between the total mass of fish and the total mass of meat.

Technically, the balance equals to $\left|\sum\limits_{i=1}^n a_i - \sum\limits_{i=1}^n b_i\right|$. The smaller the balance, the better.

In order to improve the balance, a taster was invited. He will eat exactly $m$ 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 should eat exactly $m$ grams of each dish in total.

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


-----Input-----

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

Each test case's description is preceded by a blank line. Next comes a line that contains integers $n$ and $m$ ($1 \leq n \leq 2 \cdot 10^5$; $0 \leq m \leq 10^6$). The next $n$ lines describe dishes, the $i$-th of them contains a pair of integers $a_i$ and $b_i$ ($0 \leq a_i, b_i \le 10^6$) — the masses of fish and meat in the $i$-th dish.

It is guaranteed that it is possible to eat $m$ grams of food from each dish. In other words, $m \leq a_i+b_i$ for all $i$ from $1$ to $n$ inclusive.

The sum of all $n$ values over all test cases in the test does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print on the first line the minimal balance value that can be achieved by eating exactly $m$ grams of food from each dish.

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$), where $x_i$ is how many grams of fish taster should eat from the $i$-th meal and $y_i$ is how many grams of meat.

If there are several ways to achieve a minimal balance, find any of them.


-----Examples-----

Input
8

1 5
3 4

1 6
3 4

2 2
1 3
4 2

2 4
1 3
1 7

3 6
1 7
1 8
1 9

3 6
1 8
1 9
30 10

3 4
3 1
3 2
4 1

5 4
0 7
6 4
0 8
4 1
5 3
Output
0
2 3
1
3 3
0
1 1
1 1
2
1 3
0 4
3
0 6
0 6
0 6
7
1 5
1 5
6 0
0
3 1
3 1
3 1
0
0 4
2 2
0 4
3 1
1 3


-----Note-----

None

Difficulty: HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	a = []
	b = []
	for i in range(n):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	suma = sum(a)
	sumb = sum(b)
	diff = suma - sumb
	ms = [m] * n
	ansa = [0] * n
	ansb = [0] * n
	for i in range(n):
		ma = m - b[i] if m > b[i] else 0
		mb = m - a[i] if m > a[i] else 0
		ansa[i] += ma
		ansb[i] += mb
		ms[i] -= ma + mb
		diff -= ma - mb
	for i in range(n):
		if diff > 0:
			m1 = ms[i] if ms[i] < diff else diff
			ansa[i] += m1
			diff -= m1
			ms[i] -= m1
		elif diff < 0:
			m2 = ms[i] if ms[i] < -diff else -diff
			ansb[i] += m2
			diff += m2
			ms[i] -= m2
		half = ms[i] // 2
		ansa[i] += half
		ansb[i] += ms[i] - half
		diff += ms[i] % 2
	print(abs(diff))
	for i in range(n):
		print(ansa[i], ansb[i])


import math
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
from bisect import bisect_left
from bisect import bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import deque
t = int(input())
for _ in range(t):
	input()
	(n, m) = map(int, input().split())
	res = []
	mi = 0
	ma = 0
	re = n * m
	ans = []
	ans1 = []
	for i in range(n):
		(u, v) = map(int, input().split())
		ans.append([u, v])
		ans1.append([u, v])
		l = max(m - v, 0)
		r = min(u, m)
		res.append([l, r])
		mi += l
		ma += r
		re += u - v
	sl = 2 * mi
	sr = 2 * ma
	sm = 0
	if re <= sl:
		print(abs(sl - re))
		for i in range(n):
			ans[i][0] -= res[i][0]
			ans[i][1] -= m - res[i][0]
		sm = sl
	elif re >= sr:
		print(abs(sr - re))
		for i in range(n):
			ans[i][0] -= res[i][1]
			ans[i][1] -= m - res[i][1]
		sm = sr
	else:
		print(re % 2)
		sm = re - re % 2
		diff = (sr - sm) // 2
		for i in range(n):
			if diff == 0:
				ans[i][0] -= res[i][1]
				ans[i][1] -= m - res[i][1]
			else:
				tot = res[i][1] - res[i][0]
				if diff >= tot:
					diff -= tot
					ans[i][0] -= res[i][0]
					ans[i][1] -= m - res[i][0]
				else:
					res[i][1] -= diff
					diff = 0
					ans[i][0] -= res[i][1]
					ans[i][1] -= m - res[i][1]
	for j in range(n):
		print(ans1[j][0] - ans[j][0], ans1[j][1] - ans[j][1])


for t in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	t = n * m
	q = [list(map(int, input().split())) for i in range(n)]
	x = j = k = 0
	for i in q:
		x += i[0] - i[1]
		j += min(m, i[0])
		k += min(m, i[1])
	b = t - k
	e = b if x < t - 2 * k else j if x > 2 * j - t else (t + x + 1) // 2
	print(abs(x - 2 * e + t))
	r = e - b
	for i in q:
		c = max(m - i[1], 0)
		a = min(r, min(m - c, i[0] - c))
		c += a
		r -= a
		print(f'{c} {m - c}')


for t in range(int(input())):
	input()
	(n, m) = map(int, input().split())
	nm = n * m
	mass = [list(map(int, input().split())) for i in range(n)]
	balance = max_a = max_b = 0
	for i in mass:
		balance += i[0] - i[1]
		max_a += min(m, i[0])
		max_b += min(m, i[1])
	min_a = nm - max_b
	if balance < nm - 2 * max_b:
		eat_a = min_a
	elif balance > 2 * max_a - nm:
		eat_a = max_a
	else:
		eat_a = (nm + balance + 1) // 2
	print(abs(balance - 2 * eat_a + nm))
	rest_a = eat_a - min_a
	for i in mass:
		cur_a = max(m - i[1], 0)
		add = min(rest_a, min(m - cur_a, i[0] - cur_a))
		cur_a += add
		rest_a -= add
		print(f'{cur_a} {m - cur_a}')


def resolve(n, m, pairs):
	delta = []
	(l, r) = (0, 0)
	for (a, b) in pairs:
		delta.append([0, 0, l, r])
		(da, db) = (min(a, m), min(b, m))
		delta[-1][1] = b - (m - da) - (a - da)
		delta[-1][0] = b - db - (a - (m - db))
		l += delta[-1][0]
		r += delta[-1][1]
	if r <= 0 or l >= 0:
		x = 1 if r <= 0 else 0
		ret = [str(-r if r <= 0 else l)]
		for i in range(n):
			(ab, [a, b]) = (sum(pairs[i]) - m, pairs[i])
			ret.append(f'{a - (ab - delta[i][x] >> 1)} {b - (ab + delta[i][x] >> 1)}')
	else:
		ret = ['1' if r & 1 else '0'] + [None] * n
		tot = 0
		for i in range(n - 1, -1, -1):
			x = max(-(delta[i][3] + tot), delta[i][0])
			x += x & 1 ^ delta[i][0] & 1
			(ab, [a, b]) = (sum(pairs[i]) - m, pairs[i])
			ret[i + 1] = f'{a - (ab - x >> 1)} {b - (ab + x >> 1)}'
			tot += x
	return '\n'.join(ret)
t = int(input())
ans = []
for _ in range(t):
	input()
	(n, m) = [int(_) for _ in input().split()]
	ans.append(resolve(n, m, [[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

def solve():
	SI()
	(n, m) = LI()
	ab = LLI(n)
	eat = []
	sa = sb = 0
	pre = 0
	for (a, b) in ab:
		mn = max(0, m - b)
		eat.append(mn)
		sa += a
		sb += b
		pre += mn
	d = sb - sa
	t = (m * n - d) // 2 - pre
	sa = sb = 0
	for (i, (a, b)) in enumerate(ab):
		if t > 0:
			cur = min(t, m - eat[i], a - eat[i])
			t -= cur
			eat[i] += cur
		sa += a - eat[i]
		sb += b - m + eat[i]
	print(abs(sa - sb))
	for i in range(n):
		print(eat[i], m - eat[i])
for testcase in range(II()):
	solve()


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

def main(t):
	space = input()
	(n, req) = map(int, input().split())
	tempmin = []
	tempmax = []
	temp = []
	ans = []

	def getab(i, diff):
		ans.append([(req - diff + temp[i][0] - temp[i][1]) // 2, (req + diff + temp[i][1] - temp[i][0]) // 2])
	for i in range(n):
		(maxa, maxb) = map(int, input().split())
		temp.append([maxa, maxb])
		if req > maxb:
			maxdiff = maxa - (req - maxb)
		else:
			maxdiff = maxa - (maxb - req)
		if req > maxa:
			mindiff = 0 - (maxb - (req - maxa))
		else:
			mindiff = maxa - req - maxb
		tempmin.append(mindiff)
		tempmax.append(maxdiff)
	minimum = sum(tempmin)
	needed = -minimum
	for i in range(n):
		if needed >= tempmax[i] - tempmin[i]:
			getab(i, tempmax[i])
			needed -= tempmax[i] - tempmin[i]
		elif needed >= 0:
			if needed % 2 == 1:
				getab(i, tempmin[i] + needed - 1)
				needed = 1
			else:
				getab(i, tempmin[i] + needed)
				needed = 0
		else:
			getab(i, tempmin[i])
	print(abs(needed))
	for sub in ans:
		print(sub[0], sub[1])
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1