Problem: The 2050 volunteers are organizing the "Run! Chase the Rising Sun" activity. Starting on Apr 25 at 7:30 am, runners will complete the 6km trail around the Yunqi town.

There are n+1 checkpoints on the trail. They are numbered by 0, 1, ..., n. A runner must start at checkpoint 0 and finish at checkpoint n. No checkpoint is skippable — he must run from checkpoint 0 to checkpoint 1, then from checkpoint 1 to checkpoint 2 and so on. Look at the picture in notes section for clarification.

Between any two adjacent checkpoints, there are m different paths to choose. For any 1≤ i≤ n, to run from checkpoint i-1 to checkpoint i, a runner can choose exactly one from the m possible paths. The length of the j-th path between checkpoint i-1 and i is b_{i,j} for any 1≤ j≤ m and 1≤ i≤ n.

To test the trail, we have m runners. Each runner must run from the checkpoint 0 to the checkpoint n once, visiting all the checkpoints. Every path between every pair of adjacent checkpoints needs to be ran by exactly one runner. If a runner chooses the path of length l_i between checkpoint i-1 and i (1≤ i≤ n), his tiredness is $$$min_{i=1}^n l_i,$$$ i. e. the minimum length of the paths he takes.

Please arrange the paths of the m runners to minimize the sum of tiredness of them.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10 000). Description of the test cases follows.

The first line of each test case contains two integers n and m (1 ≤ n,m ≤ 100).

The i-th of the next n lines contains m integers b_{i,1}, b_{i,2}, ..., b_{i,m} (1 ≤ b_{i,j} ≤ 10^9).

It is guaranteed that the sum of n⋅ m over all test cases does not exceed 10^4.

Output

For each test case, output n lines. The j-th number in the i-th line should contain the length of the path that runner j chooses to run from checkpoint i-1 to checkpoint i. There should be exactly m integers in the i-th line and these integers should form a permuatation of b_{i, 1}, ..., b_{i, m} for all 1≤ i≤ n.

If there are multiple answers, print any.

Example

Input


2
2 3
2 3 4
1 3 5
3 2
2 3
4 1
3 5


Output


2 3 4
5 3 1
2 3
4 1
3 5

Note

In the first case, the sum of tiredness is min(2,5) + min(3,3) + min(4,1) = 6.

<image>

In the second case, the sum of tiredness is min(2,4,3) + min(3,1,5) = 3.

Solution (in PYTHON3):

Solution:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter
import itertools


def func(n, m, array):
    all_paths = list(itertools.chain.from_iterable(array))
    sorted_path = sorted(range(len(all_paths)), key=lambda k: all_paths[k])
    choosing = {}
    choosing_list = []
    indices = [0] * n
    for val in sorted_path[:m]:
        path = val // m
        pos = val % m
        choosing_list.append((path, pos))
        if path in choosing:
            choosing[path].add(pos)
        else:
            choosing[path] = set([pos])
    shorted_paths = []
    # print(array)
    # print(choosing)
    for i in range(m):
        curr = [None] * n
        path, pos = choosing_list[i]
        curr[path] = array[path][pos]
        # print(path, pos, curr)
        for j in range(n):
            if curr[j] is None:
                while j in choosing and indices[j] in choosing[j]:
                    indices[j] += 1
                # print(indices)
                # print(indices[j])
                curr[j] = array[j][indices[j]]
                indices[j] += 1
        shorted_paths.append(curr)
        # print(curr, indices)
        # print(indices)
    # print(all_paths)
    # print(sorted_path)
    # print(choosing)
    shorted_paths = list(map(list, zip(*shorted_paths)))
    # print(shorted_paths)
    for path in shorted_paths:
        print(" ".join(str(i) for i in path))
    # return [" ".join(str(i) for i in path) for path in shorted_paths]


def main():
    num_test = int(parse_input())
    result = []
    for _ in range(num_test):
        n, m = [int(i) for i in parse_input().split()]
        array = []
        for i in range(n):
            array.append([int(i) for i in parse_input().split()])
        func(n, m, array)
    # print("\n".join(map(str, result)))


# region fastio

# BUFSIZE = 8192


# 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)
parse_input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()