You like numbers, don't you? Nastia has a lot of numbers and she wants to share them with you! Isn't it amazing?

Let a_i be how many numbers i (1 ≤ i ≤ k) you have.

An n × n matrix is called beautiful if it contains all the numbers you have, and for each 2 × 2 submatrix of the original matrix is satisfied: 

  1. The number of occupied cells doesn't exceed 3; 
  2. The numbers on each diagonal are distinct. 



Make a beautiful matrix of minimum size.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains 2 integers m and k (1 ≤ m, k ≤ 10^5) — how many numbers Nastia gave you and the length of the array a, respectively.

The second line of each test case contains k integers a_1, a_2, …, a_{k} (0 ≤ a_i ≤ m, a_1 + a_2 + … + a_{k} = m), where a_i is how many numbers i you have.

It's guaranteed that the sum of m and k in one test doesn't exceed 2 ⋅ 10^5.

Output

For each t test case print a single integer n — the size of the beautiful matrix.

In the next n lines print n integers b_{i, j} (0 ≤ b_{i, j} ≤ k; if position is empty, print b_{i, j} = 0) — the beautiful matrix b you made up. 

Example

Input


2
3 4
2 0 0 1
15 4
2 4 8 1


Output


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

Note

Note that 0 in this problem represents a blank, not a number.

Examples of possible answers for the first test case:

\begin{array}{cc} 1 & 1 \\\ 4 & 0 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 4 \\\ 1 & 0 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 0 \\\ 1 & 1 \\\ \end{array}

Examples of not beautiful matrices for the first test case:

\begin{array}{cc} 1 & 0 \\\ 4 & 1 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 4 & 1 \\\ 7 & 1 \\\ \end{array} \hspace{0,5cm} \begin{array}{cc} 1 & 0 \\\ 4 & 0 \\\ \end{array}

The example of the not beautiful matrix for the second test case:

\begin{array}{cc} 3 & 4 & 0 & 2 & 2 \\\ 3 & 2 & 3 & 3 & 0 \\\ 0 & 1 & 0 & 0 & 0 \\\ 3 & 0 & 0 & 0 & 0 \\\ 2 & 1 & 3 & 3 & 3 \\\ \end{array}

Everything is okay, except the left-top submatrix contains 4 numbers.

Source: codeforces | Difficulty: VERY_HARD
Tags: Sorting

Constructive algorithms

Greedy algorithms


Solutions:
def cheak(x):
	return x ** 2 - (x // 2) ** 2 >= m and x * (x // 2 + (1 if x % 2 != 0 else 0)) >= mx
for test in range(int(input())):
	(m, k) = (int(i) for i in input().split())
	a = [int(i) for i in input().split()]
	mx = max(a)
	z = 0
	y = m * 4
	while z != y:
		x = (z + y) // 2
		if cheak(x):
			y = x
		else:
			z = x + 1
	else:
		x = z
	a = sorted(list(map(list, zip(a, range(1, len(a) + 1)))))

	def get():
		i = len(a)
		while i != 0:
			i -= 1
			while a[i][0] > 0:
				a[i][0] -= 1
				yield a[i][1]
		yield 0
	mt = [[0 for i in range(x)] for j in range(x)]
	t = 1
	it = get()
	for i in range(0, x, 2):
		if t == 0:
			break
		for j in range(1, x, 2):
			t = next(it)
			if t:
				mt[i][j] = t
			else:
				break
	for i in range(0, x, 2):
		if t == 0:
			break
		for j in range(0, x, 2):
			t = next(it)
			if t:
				mt[i][j] = t
			else:
				break
	for i in range(1, x, 2):
		if t == 0:
			break
		for j in range(0, x, 2):
			t = next(it)
			if t:
				mt[i][j] = t
			else:
				break
	print(len(mt))
	for i in mt:
		print(*i)


from math import ceil
import heapq

def solve(m, k, a):
	N = 1
	free = ceil(N / 2) ** 2
	A = N // 2 * ceil(N / 2)
	B = N // 2 * ceil(N / 2)
	while free + A + B < m:
		N += 1
		free = ceil(N / 2) ** 2
		A = N // 2 * ceil(N / 2)
		B = N // 2 * ceil(N / 2)
	mx_freq = max(a)
	while free + B < mx_freq:
		N += 1
		free = ceil(N / 2) ** 2
		A = N // 2 * ceil(N / 2)
		B = N // 2 * ceil(N / 2)
	ans = [[0] * N for _ in range(N)]
	A = [(i, j) for i in range(1, N, 2) for j in range(0, N, 2)]
	B = [(i, j) for i in range(0, N, 2) for j in range(1, N, 2)]
	F = [(i, j) for i in range(0, N, 2) for j in range(0, N, 2)]
	pq = []
	for i in range(k):
		if a[i] > 0:
			heapq.heappush(pq, (-a[i], i + 1))
	l = len(pq)
	cur_ele = None
	cur_freq = 0
	while B:
		if not pq and cur_freq == 0:
			break
		if cur_freq == 0:
			X = heapq.heappop(pq)
			cur_ele = X[1]
			cur_freq = -X[0]
		(i, j) = B.pop()
		ans[i][j] = cur_ele
		cur_freq -= 1
	later = []
	if len(pq) == l - 1:
		later.append([cur_ele, cur_freq])
		cur_ele = None
		cur_freq = 0
	while A:
		if not pq and cur_freq == 0:
			break
		if cur_freq == 0:
			X = heapq.heappop(pq)
			cur_ele = X[1]
			cur_freq = -X[0]
		(i, j) = A.pop()
		ans[i][j] = cur_ele
		cur_freq -= 1
	if later:
		(ele, freq) = later.pop()
		if cur_freq:
			heapq.heappush(pq, (-cur_freq, cur_ele))
		cur_ele = ele
		cur_freq = freq
	while pq or cur_freq:
		if cur_freq == 0:
			X = heapq.heappop(pq)
			cur_ele = X[1]
			cur_freq = -X[0]
		while cur_freq:
			(i, j) = F.pop()
			ans[i][j] = cur_ele
			cur_freq -= 1
	print(N)
	for row in ans:
		print(*row)
	return -1
for nt in range(int(input())):
	(m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	solve(m, k, a)


from math import sqrt, ceil
import sys

def putin():
	return map(int, sys.stdin.readline().split())

def sol():
	(m, k) = putin()
	A = list(putin())
	A = sorted(list(enumerate(A)), reverse=True, key=lambda x: x[1])
	B = []
	C = []
	for elem in A:
		if len(B) > len(C):
			C += [elem[0] + 1] * elem[1]
		else:
			B += [elem[0] + 1] * elem[1]
	if len(C) > len(B):
		(C, B) = (B, C)
	even_n = ceil(max(sqrt(4 * m / 3), sqrt(2 * len(B))))
	if even_n % 2 == 1:
		even_n += 1
	odd_n = even_n - 1
	if odd_n ** 2 - (odd_n - 1) ** 2 / 4 >= m and odd_n * (odd_n + 1) / 2 >= len(B):
		n = odd_n
	else:
		n = even_n
	if n % 2 == 0:
		C += [0] * (3 * n ** 2 // 4 - len(B) - len(C))
	else:
		C += [0] * (n ** 2 - (n - 1) ** 2 // 4 - len(B) - len(C))
	if n % 2 == 0:
		border = n ** 2 // 4
	else:
		border = (n - 1) * (n + 1) // 4
	(B, D) = (B[:border], B[border:])
	D += C[border:]
	C = C[:border]
	B_cnt = 0
	C_cnt = 0
	D_cnt = 0
	print(n)
	for i in range(n):
		for j in range(n):
			if i % 2 == 1 and j % 2 == 1:
				print(0, end=' ')
			elif i % 2 == 1:
				print(B[B_cnt], end=' ')
				B_cnt += 1
			elif j % 2 == 1:
				print(C[C_cnt], end=' ')
				C_cnt += 1
			else:
				print(D[D_cnt], end=' ')
				D_cnt += 1
		print()
for iter in range(int(sys.stdin.readline())):
	sol()


from random import randint
DEBUG = 0
for _ in range(int(input())):
	if DEBUG:
		k = randint(2, 4)
		maxcnt = randint(1, 100)
		cnt = [randint(1, maxcnt) for i in range(k)]
		m = sum(cnt)
		cnt = sorted(enumerate(cnt), key=lambda x: -x[1])
	else:
		(m, k) = list(map(int, input().split()))
		cnt = sorted(enumerate(map(int, input().split())), key=lambda x: -x[1])
	l = 0
	r = m
	while r - l > 1:
		mid = (r + l) // 2
		if mid * ((mid + 1) // 2) >= cnt[0][1] and (mid // 2) ** 2 + m <= mid ** 2:
			r = mid
		else:
			l = mid
	size = r
	queue = []
	queue.extend([(i, j) for i in range(1, size, 2) for j in range(0, size, 2)])
	queue.extend([(i, j) for i in range(0, size, 2) for j in range(0, size, 4)])
	queue.extend([(i, j) for i in range(0, size, 2) for j in range(2, size, 4)])
	queue.extend([(i, j) for i in range(0, size, 2) for j in range(1, size, 2)])
	a = [[0] * size for i in range(size)]
	ind = 0
	rest = cnt[ind][1]
	for (i, j) in queue:
		while not rest:
			ind += 1
			if ind < k:
				rest = cnt[ind][1]
			else:
				break
		else:
			a[i][j] = cnt[ind][0] + 1
			rest -= 1
			continue
		break
	if not DEBUG:
		print(size)
		for row in a:
			print(*row)
	if DEBUG:
		for i in range(size - 1):
			for j in range(size - 1):
				if a[i][j] == a[i + 1][j + 1] != 0 or a[i + 1][j] == a[i][j + 1] != 0:
					print('Oops...')
					print(m, k)
					print(*cnt)
					break
			else:
				continue
			break
		else:
			continue
		break


from math import sqrt, ceil
for testcase_testcase in range(int(input())):
	(m, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A = sorted(list(enumerate(A)), reverse=True, key=lambda x: x[1])
	B = []
	C = []
	for elem in A:
		if len(B) > len(C):
			C += [elem[0] + 1] * elem[1]
		else:
			B += [elem[0] + 1] * elem[1]
	if len(C) > len(B):
		(C, B) = (B, C)
	even_n = ceil(max(sqrt(4 * m / 3), sqrt(2 * len(B))))
	if even_n % 2 == 1:
		even_n += 1
	odd_n = even_n - 1
	n = odd_n if odd_n ** 2 - (odd_n - 1) ** 2 / 4 >= m and odd_n * (odd_n + 1) / 2 >= len(B) else even_n
	C += [0] * (3 * n ** 2 // 4 - len(B) - len(C)) if n % 2 == 0 else [0] * (n ** 2 - (n - 1) ** 2 // 4 - len(B) - len(C))
	border = n ** 2 // 4 if n % 2 == 0 else (n - 1) * (n + 1) // 4
	(B, D) = (B[:border], B[border:])
	D += C[border:]
	C = C[:border]
	B_cnt = 0
	C_cnt = 0
	D_cnt = 0
	print(n)
	for i in range(n):
		for j in range(n):
			if i % 2 == 1 and j % 2 == 1:
				print(0, end=' ')
			elif i % 2 == 1:
				print(B[B_cnt], end=' ')
				B_cnt += 1
			elif j % 2 == 1:
				print(C[C_cnt], end=' ')
				C_cnt += 1
			else:
				print(D[D_cnt], end=' ')
				D_cnt += 1
		print()


from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

class UF:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n
		self.size = AI(n, 1)
		self.edge = A(n)

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			self.edge[pu] += 1
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			self.edge[pu] += self.edge[pv] + 1
			self.size[pu] += self.size[pv]
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv
			self.edge[pv] += self.edge[pu] + 1
			self.size[pv] += self.size[pu]

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = AI(n, inf)
	d[s] = 0
	heap = [(0, s)]
	vis = A(n)
	while heap:
		(dis, u) = heappop(heap)
		if vis[u]:
			continue
		vis[u] = 1
		for (v, w) in graph[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

def check(i, j):
	if not ans[i][j]:
		return True
	for (ni, nj) in [[i - 1, j - 1], [i + 1, j + 1], [i + 1, j - 1], [i - 1, j + 1]]:
		if 0 <= ni < l and 0 <= nj < l and (ans[ni][nj] == ans[i][j]):
			return False
	return True
t = N()
for i in range(t):
	(m, k) = RL()
	a = RLL()
	l = 1
	r = m
	ma = max(a)
	while l < r:
		n = l + r >> 1
		if n & 1:
			if (3 * n ** 2 + 2 * n - 1) // 4 >= m and (n + 1) * n // 2 >= ma:
				r = n
			else:
				l = n + 1
		elif 3 * n * n // 4 >= m and n * n // 2 >= ma:
			r = n
		else:
			l = n + 1
	c = {}
	res = []
	for i in range(k):
		if a[i]:
			res += [i + 1] * a[i]
			c[i + 1] = a[i]
	res.sort(key=lambda x: -c[x])
	ans = A2(l, l)
	p = 0
	for i in range(0, l, 2):
		for j in range(0, l):
			ans[i][j] = res[p]
			p += 1
			if p == len(res):
				break
		if p == len(res):
			break
	if p < len(res):
		for i in range(1, l, 2):
			for j in range(0, l, 2):
				ans[i][j] = res[p]
				p += 1
				if p == len(res):
					break
			if p == len(res):
				break
	(ci, cj) = (0, 0)
	for i in range(0, l, 2):
		for j in range(1, l):
			if not check(i, j):
				(ans[i][j], ans[ci][cj]) = (ans[ci][cj], ans[i][j])
				cj += 2
				if cj >= l:
					cj = 0
					ci = ci + 2
	print(l)
	for r in ans:
		print(*r)