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 \leq i \leq 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 \leq m1,m2 \leq K$ and $0 \leq c1,c2 \leq 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 \leq c1,c2 \leq N$.
- The output should be valid and should satisfy Salmon's goal.

-----Constraints-----
- $T=10$
- $2 \leq N \leq 10^5$ 
- $2 \leq K \leq 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 \leq N \leq 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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def abc(balls, n):\n y = n\n i = 0\n while(y):\n  if i<=n and balls[i]==0:\n   i = i+1\n   continue\n  c1 = i\n  if balls[i]>=2:\n   balls[i] -= 2\n   m1 = 2\n   c2 = n\n   m2 = 0\n  else:\n   m1 = 1\n   balls[i] = 0\n   j = i\n   while(j<n and balls[j]==0):\n    j = j+1\n   i = j\n   c2 = i\n   balls[i] -= 1\n   m2 = 1\n  print(c1,m1,c2,m2)\n  y = y-1\n   \n \nfor _ in range(int(input())):\n n, k = list(map(int, input().split()))\n balls = list(map(int, input().split()))\n \n if k==2:\n  abc(balls, n)\n  continue\n \n # y = n\n # missing = n\n # temp = []\n # for i in range(i+1):\n #     if balls[i]!=0:\n #         temp.append(i)\n #     else:\n #         missing = i\n #         n = n-1\n   \n arr = []\n for i in range(n+1):\n  arr.append([balls[i], i])\n arr = sorted(arr, key=lambda x:x[0])\n # print(arr)\n \n i = 0\n j = n\n y = n\n while(arr[j][0] == 0):\n  j = j-1\n \n while(y):\n  if i<=n and arr[i][0] == 0:\n   i = i+1\n   continue\n  x = k\n  c1 = arr[i][1]\n  if x<=arr[i][0]:\n   arr[i][0] = arr[i][0]-x;\n   m1 = k\n   m2 = 0\n   c2 = n\n  else:\n   x = k - arr[i][0]\n   m1 = arr[i][0]\n   arr[i][0] = 0\n   c2 = arr[j][1]\n   m2 = min(arr[j][0], x)\n   arr[j][0] = max(arr[j][0]-x, 0)\n  \n  if(arr[j][0] == 0):\n   j = j-1\n  if(arr[i][0] == 0):\n   i = i+1\n  print(c1,m1,c2,m2)\n  y = y-1\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13981