Salmon loves to be a tidy person. One day, when he looked at the mess that he made after playing with his rubber ducks, he felt awful. Now he wants to clean up his mess, by placing his ducks into boxes.

Each rubber duck has a color. There are a total of $N+1$ colors, numbered from $0$ to $N$. Salmon wants to place his $N*K$ ducks into $N$ boxes, each of which can fit $K$ ducks. Each duck should be placed inside a box.

Salmon is very particular when it comes to how many colors he can place in each box. Since Salmon doesn't like lots of colors mixing together he only wants to have a maximum of $2$ distinct colors per box.

Please help Salmon achieve this goal!    
It can be shown that there will always be at least one valid solution under given constraints.   
If there are multiple correct solutions, you may output any one of them.   

------  Input: ------
The first line contains an integer $T$, denoting the number of testcases. $T$ testcases will follow, each containing two lines.   
The first line of each testcase contains two space-separated integers $N$ and $K$.   
The second line of each testcase contains $N+1$  space-separated integers. The $i+1$-th integer denotes the number of ducks with color-$i$ where $0 ≤ i ≤ N$

------  Output: ------

Output $N$ lines for each testcase. 
The $i$-th line of a testcase should contain $4$ space-separated integers $c1, m1, c2, m2$ respectively which denotes that that are $m1$ ducks of color-$c1$ and $m2$ ducks of color-$c2$ inside the $i$-th box where $0 ≤ m1,m2 ≤ K$ and $0 ≤ c1,c2 ≤ N$. 
Note that even if you have only one color to put inside the $i$-th box, you should still output $4$ space-separated integers and keep either $m1$ or $m2$ as $0$. And $0 ≤ c1,c2 ≤ N$.
The output should be valid and should satisfy Salmon's goal.

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

$T=10$
$2 ≤ N ≤ 10^{5}$ 
$2 ≤ K ≤ 10^{5}$ 
Total ducks for each test case is exactly $N*K$
There can be a color with $0$ ducks
 
------  Subtasks ------

Subtask 1 [20 points]: $2 ≤ N ≤ 10$, $K=2$  
Subtask 2 [30 points]: $N=2$, $K=5$
Subtask 3 [50 points]: original constraints

------  Sample Input: ------

1
2 4
3 4 1

------  Sample Output: ------

2 1 1 3
1 1 0 3

------  Explanation: ------

In the given testcase, Salmon has $N=2$ boxes, each of size $K=4$ and there are total $N*K=8$ ducks.   
The first box is filled with $1$ duck of color-$2$ and $3$ ducks of color-$1$ and the second box is filled with $1$ duck of color-$1$ and $3$ ducks of color-$0$.   
Each duck is inside a box and each box has at most two distinct colors. Also each box contains exactly $K=4$ ducks.

Difficulty: HARD
Tags: Constructive algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = n
	y = 0
	a = [int(x) for x in input().split()]
	store = []
	for i in range(n + 1):
		store.append([a[i], i])
	store.sort()
	for i in range(n):
		print(store[y][1], store[y][0], store[x][1], k - store[y][0])
		store[x][0] -= k - store[y][0]
		if store[x][0] < k:
			store[y] = store[x]
			x -= 1
		else:
			y += 1


def answer():
	all = [[a[i], i] for i in range(n + 1)]
	all.sort()
	(p1, p2) = (0, n)
	for i in range(n):
		if all[p1][0] >= k:
			v1 = k
			all[p1][0] -= v1
		else:
			v1 = all[p1][0]
			all[p1][0] -= v1
		v2 = min(k - v1, all[p2][0])
		all[p2][0] -= v2
		print(all[p1][1], v1, all[p2][1], v2)
		if all[p2][0] < k:
			all[p1] = all[p2]
			p2 -= 1
			p1 -= 1
		p1 += 1
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	answer()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	lis = []
	for i in range(len(l)):
		lis.append([l[i], i])
	lis.sort(reverse=True)
	(i, c1, m1, c2, m2, j) = (0, 0, 0, 0, 0, len(lis) - 1)
	while n != 0:
		if lis[j][0] < k:
			(c1, m1) = (lis[j][1], lis[j][0])
			lis[j][0] -= m1
			if lis[j][0] == 0:
				j -= 1
		else:
			(c1, m1) = (lis[j][1], k)
			lis[j][0] -= m1
			if lis[j][0] == 0:
				j -= 1
		if k - m1 < lis[i][0]:
			(m2, c2) = (k - m1, lis[i][1])
			lis[i][0] -= m2
			if lis[i][0] == 0:
				i += 1
		else:
			(m2, c2) = (lis[i][0], lis[i][1])
			lis[i][0] -= m2
			if lis[i][0] == 0:
				i += 1
		if lis[i][0] + lis[j][0] < k and i != j:
			lis[j + 1] = lis[i]
			i += 1
			j += 1
		print(c1, m1, c2, m2)
		n -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	li = []
	x = n
	y = 0
	for i in range(n + 1):
		li.append([a[i], i])
	li.sort()
	for i in range(n):
		print(li[y][1], li[y][0], li[x][1], k - li[y][0])
		li[x][0] -= k - li[y][0]
		if li[x][0] < k:
			li[y] = li[x]
			x -= 1
		else:
			y += 1


import math
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = []
	indx = 0
	for i in arr:
		l.append([indx, i])
		indx += 1
	l.sort(key=lambda x: x[1])
	st = 0
	en = n
	for i in range(n):
		(m1, c1, m2, c2) = (0, 0, 0, 0)
		m1 = l[st][1]
		m2 = k - m1
		c1 = l[st][0]
		c2 = l[en][0]
		l[en][1] -= m2
		if l[en][1] < k:
			l[st] = l[en]
			en -= 1
		else:
			st += 1
		print(c1, m1, c2, m2)