Meanwhile, Candace and Stacy are busy planning to attend the concert of the famous Love Händel. Jeremy will also be attending the event. Therefore, Candace plans to offer the best possible gift to Jeremy.
Candace has $N$ strings, each of length $M$. Each character of each string can either be a lowercase English letter or the character '#'. She denotes the substring of $i$-$th$ string starting from the $l$-$th$ character and ending with the $r$-$th$ character as $S_{i}[l, r]$. She has to choose a list $a$ of $N - 1$ numbers such that  
- $1 \leq a_1 \leq a_2 \leq a_3 \leq ... \leq a_{N-1} \leq  M$.
- The final gift string is obtained by appending the substrings $S_{1}[1, a_{1}]$, $S_{2}[a_{1}, a_{2}]$, $S_{3}[a_{2}, a_{3}]$, .., $S_{N-1}[a_{N-2}, a_{N-1}]$, $S_{N}[a_{N-1}, M]$.
- Candace considers the gift to be the most beautiful one if the final gift string is the lexicographically smallest possible string and it doesn't contain the '#' character.
Let $P$ = $S_{1}[1, a_{1}]$ + $S_{2}[a_{1}, a_{2}]$ + $S_{3}[a_{2}, a_{3}]$ + .., + $S_{N-1}[a_{N-2}, a_{N-1}]$ + $S_{N}[a_{N-1}, M]$, then $P$ should be the lexicographically smallest string  possible and it should not contain '#' character, where '+' denotes concatenation of two substrings.
Help Candace find the best possible gift string quickly as she does not want Jeremy to wait for her. Also, it is guaranteed that at least one such valid string exists.

-----Input-----
- The first line contains a single integer $T$ denoting the number of testcases.
- The first line of each test case contains $2$ space separated integers denoting the values of $N$ and $M$ respectively.
- $N$ lines follow. Each line contains a string $S_i$ of length $M$ as described above.

-----Output-----
For every test case, print a line containing lexicographically lowest possible gift string.

-----Constraints-----
- $1 \leq T \leq 10^4$
- $1 \leq N, M \leq 10^6$
- $|S_i| = M$
- All $S_i$ will contain either a lower English letter ('a' to 'z' ) or the character '#' (ASCII $35$).
- Sum of $N * M$ over all test cases for a particular test file does not exceed $10^7$.
- It is guaranteed that a valid solution will always exist.

-----Sample Input-----
2
3 3
xab
a#z
caa
5 4
pyqs
vcot
qbiu
lihj
uvmz

-----Sample Output-----
xabza
pvcbihjz

-----Explanation-----
For test $1$:
The array $a$ chosen is: $[3, 3]$
The resulting string $P$ is formed by = $S_{1}[1, 3]$ + $S_{2}[3, 3]$ + $S_{3}[3, 3]$ = xabza
For test $2$:
The array $a$ chosen is: $[1, 2, 3, 4]$
The resulting string $P$ is formed by = $S_{1}[1, 1]$ + $S_{2}[1, 2]$ + $S_{3}[2, 3]$ + $S_{4}[3, 4]$ + $S_{5}[4, 4]$ = pvcbihjz

```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 = '# import all important libraries and inbuilt functions\n\nfrom fractions import Fraction\nimport numpy as np\nimport sys,bisect,copyreg,copy,statistics,os\nfrom math import *\nfrom collections import Counter,defaultdict,deque,OrderedDict   \nfrom itertools import combinations,permutations,accumulate \nfrom numpy.linalg import matrix_power as mp\nfrom bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right\nfrom statistics import mode\nfrom functools import reduce,cmp_to_key \nfrom io import BytesIO, IOBase\nfrom scipy.spatial import ConvexHull\nfrom heapq import *\nfrom decimal import *\nfrom queue import Queue,PriorityQueue\nfrom re import sub,subn\n\n# end of library import\n\n# map system version faults\nif sys.version_info[0] < 3:\n    from builtins import xrange as range\n    from future_builtins import ascii, filter, hex, map, oct, zip\n\n# template of many functions used in competitive programming can add more later \n# based on need we will use this commonly.\n\n# bfs in a graph\ndef bfs(adj,v): # a schema of bfs\n    visited=[False]*(v+1);q=deque()\n    while q:pass\n\n# definition of vertex of a graph\ndef graph(vertex): return [[] for i in range(vertex+1)]\n\ndef powermodulo(x, y, p) : \n    res = 1;x = x % p        \n    if (x == 0) : return 0  \n    while (y > 0) : \n        if ((y & 1) == 1) :   res = (res * x) % p \n        y = y >> 1 \n        x = (x * x) % p           \n    return res\n\ndef lcm(a,b): return (a*b)//gcd(a,b)\n\n# most common list in a array of lists\ndef most_frequent(List):return Counter(List).most_common(1)[0][0]\n\n# element with highest frequency\ndef most_common(List):return(mode(List))\n\n#In number theory, the Chinese remainder theorem states that \n#if one knows the remainders of the Euclidean division of an integer n by \n#several integers, then one can determine uniquely the remainder of the \n#division of n by the product of these integers, under the condition \n#that the divisors are pairwise coprime.\ndef chinese_remainder(a, p):\n    prod = reduce(op.mul, p, 1);x = [prod // pi for pi in p]\n    return sum(a[i] * powermodulo(x[i], p[i] - 2, p[i]) * x[i] for i in range(len(a))) % prod\n\n# make a matrix\ndef createMatrix(rowCount, colCount, dataList):   \n    mat = []\n    for i in range (rowCount):\n        rowList = []\n        for j in range (colCount):\n            if dataList[j] not in mat:rowList.append(dataList[j])\n        mat.append(rowList) \n    return mat\n\n# input for a binary tree\ndef readTree(): \n    v=int(inp());adj=[set() for i in range(v+1)]\n    for i in range(v-1):u1,u2=In(); adj[u1].add(u2);adj[u2].add(u1)\n    return adj,v\n    \n# sieve of prime numbers    \ndef sieve():\n    li=[True]*1000001;li[0],li[1]=False,False;prime=[]\n    for i in range(2,len(li),1):\n        if li[i]==True:\n            for j in range(i*i,len(li),i):li[j]=False    \n    for i in range(1000001):\n        if li[i]==True:prime.append(i)\n    return prime\n\n#count setbits of a number.\ndef setBit(n):\n    count=0\n    while n!=0:n=n&(n-1);count+=1\n    return count\n\n# sum of digits of a number\ndef digitsSum(n):\n    if n == 0:return 0\n    r = 0\n    while n > 0:r += n % 10;n //= 10\n    return r\n\n# ncr efficiently\ndef ncr(n, r):\n    r = min(r, n - r);numer = reduce(op.mul, list(range(n, n - r, -1)), 1);denom = reduce(op.mul, list(range(1, r + 1)), 1)\n    return numer // denom  # or / in Python 2\n\n#factors of a number\ndef factors(n):return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))\n\n#prime fators of a number\ndef prime_factors(n):\n    i = 2;factors = []\n    while i * i <= n:\n        if n % i:i += 1\n        else:n //= i;factors.append(i)\n    if n > 1:factors.append(n)\n    return len(set(factors))\n\ndef prefixSum(arr):\n    for i in range(1, len(arr)):arr[i] = arr[i] + arr[i-1]\n    return arr    \n\ndef binomial_coefficient(n, k):\n    if 0 <= k <= n:\n        ntok = 1;ktok = 1\n        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1\n        return ntok // ktok\n    else:return 0\n \ndef powerOfK(k, max):\n    if k == 1:return [1]\n    if k == -1:return [-1, 1] \n    result = [];n = 1\n    while n <= max:result.append(n);n *= k\n    return result\n\n# maximum subarray sum use kadane\'s algorithm\ndef kadane(a,size):\n    max_so_far = 0;max_ending_here = 0 \n    for i in range(0, size):\n        max_ending_here = max_ending_here + a[i]\n        if (max_so_far < max_ending_here):max_so_far = max_ending_here \n        if max_ending_here < 0:max_ending_here = 0\n    return max_so_far                                    \n                  \ndef divisors(n):\n    result = []\n    for i in range(1,ceil(sqrt(n))+1):\n        if n%i == 0:\n            if n/i == i:result.append(i)\n            else:result.append(i);result.append(n/i)\n    return result\n\ndef sumtilln(n): return ((n*(n+1))//2)\n\ndef isPrime(n) : \n\tif (n <= 1) :return False\n\tif (n <= 3) :return True\n\tif (n % 2 == 0 or n % 3 == 0) :return False\n\tfor i in range(5,ceil(sqrt(n))+1,6):\n\t\tif (n % i == 0 or n % (i + 2) == 0) :return False\n\treturn True\n\ndef isPowerOf2(n):\n    while n % 2 == 0:n //= 2\n    return (True if n == 1 else False)\n\ndef power2(n):\n    k = 0\n    while n % 2 == 0:k += 1;n //= 2\n    return k\n\ndef sqsum(n):return ((n*(n+1))*(2*n+1)//6)\n    \ndef cusum(n):return ((sumn(n))**2)\n\ndef pa(a):\n    for i in range(len(a)):print(a[i], end = " ")\n    print()\n\ndef pm(a,rown,coln):\n    for i in range(rown):\n        for j in range(coln):print(a[i][j],end = " ")\n        print()\n\ndef pmasstring(a,rown,coln):\n    for i in range(rown):\n        for j in range(coln):print(a[i][j],end = "")\n        print()\n        \ndef isPerfectSquare(n):return pow(floor(sqrt(n)),2) == n\n\ndef nC2(n,m):return (((n*(n-1))//2) % m)\n\ndef modInverse(n,p):return powermodulo(n,p-2,p)\n\ndef ncrmodp(n, r, p):  \n\tnum = den = 1\n\tfor i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p \n\treturn (num * powermodulo(den,p - 2, p)) % p \n\ndef reverse(string):return "".join(reversed(string))        \n\ndef listtostr(s):return \' \'.join([str(elem) for elem in s]) \n\ndef binarySearch(arr, l, r, x): \n\twhile l <= r: \n\t\tmid = l + (r - l) // 2; \n\t\tif arr[mid] == x:return mid \n\t\telif arr[mid] < x:l = mid + 1\n\t\telse:r = mid - 1\n\treturn -1\n\ndef isarrayodd(a):\n    r = True\n    for i in range(len(a)):\n        if a[i] % 2 == 0:\n            r = False\n            break\n    return r\n\ndef isPalindrome(s):return s == s[::-1] \n\ndef gt(x,h,c,t):return ((x*h+(x-1)*c)/(2*x-1))\n\ndef CountFrequency(my_list): \n    freq = {} \n    for item in my_list:freq[item] = (freq[item] + 1 if (item in freq) else 1)\n    return freq\n\ndef CountFrequencyasPair(my_list1,my_list2,freq): \n    for item in my_list1:freq[item][0] = (freq[item][0] + 1 if (item in freq) else 1)\n    for item in my_list2:freq[item][1] = (freq[item][1] + 1 if (item in freq) else 1)     \n    return freq \n \ndef binarySearchCount(arr, n, key):   \n    left = 0;right = n - 1;count = 0  \n    while (left <= right):  \n        mid = int((right + left) / 2) \n        if (arr[mid] <= key):count,left = mid + 1,mid + 1\n        else:right = mid - 1      \n    return count\n\ndef primes(n):\n  sieve,l = [True] * (n+1),[]\n  for p in range(2, n+1):\n    if (sieve[p]):\n      l.append(p)\n      for i in range(p, n+1, p):sieve[i] = False\n  return l\n\ndef Next_Greater_Element_for_all_in_array(arr): \n\ts,n,reta,retb = list(),len(arr),[],[];arr1 = [list([0,i]) for i in range(n)]\n\tfor i in range(n - 1, -1, -1): \n\t\twhile (len(s) > 0 and s[-1][0] <= arr[i]):s.pop() \n\t\tif (len(s) == 0):arr1[i][0] = -1\t\t\t\t\t\n\t\telse:arr1[i][0] = s[-1]\t \n\t\ts.append(list([arr[i],i]))\t\t\n\tfor i in range(n):reta.append(list([arr[i],i]));retb.append(arr1[i][0])\n\treturn reta,retb\n\ndef polygonArea(X,Y,n):   \n    area = 0.0;j = n - 1\n    for i in range(n):area += (X[j] + X[i]) * (Y[j] - Y[i]);j = i   \n    return abs(area / 2.0)\n \n#defining a LRU Cache\n# where we can set values and get values based on our requirement\nclass LRUCache: \n\t# initialising capacity \n\tdef __init__(self, capacity: int): \n\t\tself.cache = OrderedDict() \n\t\tself.capacity = capacity \n\n\t# we return the value of the key \n\t# that is queried in O(1) and return -1 if we \n\t# don\'t find the key in out dict / cache. \n\t# And also move the key to the end \n\t# to show that it was recently used. \n\tdef get(self, key: int) -> int: \n\t\tif key not in self.cache:return -1\n\t\telse:self.cache.move_to_end(key);return self.cache[key] \n\n\t# first, we add / update the key by conventional methods. \n\t# And also move the key to the end to show that it was recently used. \n\t# But here we will also check whether the length of our \n\t# ordered dictionary has exceeded our capacity, \n\t# If so we remove the first key (least recently used) \n\tdef put(self, key: int, value: int) -> None: \n\t\tself.cache[key] = value;self.cache.move_to_end(key) \n\t\tif len(self.cache) > self.capacity:self.cache.popitem(last = False)\n\nclass segtree:\n    def __init__(self,n):\n        self.m = 1\n        while self.m < n:self.m *= 2\n        self.data = [0] * (2 * self.m)\n    def __setitem__(self,i,x):\n        x = +(x != 1);i += self.m;self.data[i] = x;i >>= 1\n        while i:self.data[i] = self.data[2 * i] + self.data[2 * i + 1];i >>= 1\n    def __call__(self,l,r):\n        l += self.m;r += self.m;s = 0\n        while l < r:\n            if l & 1:s += self.data[l];l += 1\n            if r & 1:r -= 1;s += self.data[r]\n            l >>= 1;r >>= 1\n        return s        \n\nclass FenwickTree:\n  def __init__(self, n):self.n = n;self.bit = [0]*(n+1)  \n  def update(self, x, d):\n    while x <= self.n:self.bit[x] += d;x += (x & (-x))  \n  def query(self, x):\n    res = 0\n    while x > 0:res += self.bit[x];x -= (x & (-x))\n    return res\n  def range_query(self, l, r):return self.query(r) - self.query(l-1)        \n# can add more template functions here\n    \n# end of template functions\n\n# To enable the file I/O i the below 2 lines are uncommented.\n# read from in.txt if uncommented\nif os.path.exists(\'in.txt\'): sys.stdin=open(\'in.txt\',\'r\')\n# will print on Console if file I/O is not activated\nif os.path.exists(\'out.txt\'): sys.stdout=open(\'out.txt\', \'w\')\n\n# inputs template\n#for fast input we areusing sys.stdin\ndef inp(): return sys.stdin.readline().strip()\n\n#for fast output, always take string\ndef out(var): sys.stdout.write(str(var))  \n\n# cusom base input needed for the program\ndef I():return (inp())\ndef II():return (int(inp()))\ndef FI():return (float(inp()))\ndef SI():return (list(str(inp())))\ndef MI():return (map(int,inp().split()))\ndef LI():return (list(MI()))\ndef SLI():return (sorted(LI()))\ndef MF():return (map(float,inp().split()))\ndef LF():return (list(MF()))\n\n# end of inputs template\n\n# common modulo values used in competitive programming\nMOD = 998244353\nmod = 10**9+7\n\n# any particular user-defined functions for the code.\n# can be written here.  \ndef solve():\n    n,m = MI()\n    ss = []\n    for _ in range(n):\n        ss.append(list(I()) + [\'#\'])\n    ss.append([\'#\']*(m+1))\n    for i in range(n-1, -1, -1):\n        for j in range(m-1, -1, -1):\n            if ss[i+1][j] == \'#\' and ss[i][j+1] == \'#\' and (i,j) != (n-1, m-1):\n                ss[i][j] = \'#\'\n    res = [ss[0][0]]\n    cend = {(0,0)}\n    for _ in range(n+m-2):\n        ncend = set()\n        mn = \'z\'\n        for i,j in cend:\n            if ss[i+1][j] != \'#\' and ss[i+1][j] <= mn:\n                ncend.add((i+1, j))\n                mn = ss[i+1][j]\n            if ss[i][j+1] != \'#\' and ss[i][j+1] <= mn:\n                ncend.add((i, j+1))\n                mn = ss[i][j+1]\n        res.append(mn)\n        cend = {(i,j) for (i,j) in ncend if ss[i][j] == mn}\n\n    print(\'\'.join(res))\n# end of any user-defined functions\n\n# main functions for execution of the program.\ndef __starting_point():  \n    # execute your program from here.\n    # start your main code from here\n        \n    # Write your code here\n    for _ in range(II()):solve()\n                    \n    # end of main code\n    # end of program\n\n# This program is written by :\n#   Shubham Gupta\n#   B.Tech (2019-2023)\n#   Computer Science and Engineering,\n#   Department of EECS\n#   Contact No:8431624358\n#   Indian Institute of Technology(IIT),Bhilai\n#   Sejbahar,\n#   Datrenga,\n#   Raipur,\n#   Chhattisgarh\n#   492015\n\n#   THANK YOU FOR \n#YOUR KIND PATIENCE FOR READING THE PROGRAM.    \n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: