You are given $n$ permutations $a_1, a_2, \dots, a_n$, each of length $m$. Recall that a permutation of length $m$ is a sequence of $m$ distinct integers from $1$ to $m$.

Let the beauty of a permutation $p_1, p_2, \dots, p_m$ be the largest $k$ such that $p_1 = 1, p_2 = 2, \dots, p_k = k$. If $p_1 \neq 1$, then the beauty is $0$.

The product of two permutations $p \cdot q$ is a permutation $r$ such that $r_j = q_{p_j}$.

For each $i$ from $1$ to $n$, print the largest beauty of a permutation $a_i \cdot a_j$ over all $j$ from $1$ to $n$ (possibly, $i = j$).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n \le 5 \cdot 10^4$; $1 \le m \le 10$) — the number of permutations and the length of each permutation.

The $i$-th of the next $n$ lines contains a permutation $a_i$ — $m$ distinct integers from $1$ to $m$.

The sum of $n$ doesn't exceed $5 \cdot 10^4$ over all testcases.


-----Output-----

For each testcase, print $n$ integers. The $i$-th value should be equal to the largest beauty of a permutation $a_i \cdot a_j$ over all $j$ ($1 \le j \le n$).


-----Examples-----

Input
3
3 4
2 4 1 3
1 2 4 3
2 1 3 4
2 2
1 2
2 1
8 10
3 4 9 6 10 2 7 8 1 5
3 9 1 8 5 7 4 10 2 6
3 10 1 7 5 9 6 4 2 8
1 2 3 4 8 6 10 7 9 5
1 2 3 4 10 6 8 5 7 9
9 6 1 2 10 4 7 8 3 5
7 9 3 2 5 6 4 8 1 10
9 4 3 7 5 6 1 10 8 2
Output
1 4 4 
2 2 
10 8 1 6 8 10 1 7


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

String algorithms

Sorting

Mathematics

Data structures


Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	T = {}
	A = []
	for _ in range(n):
		I = list(map(int, input().split()))
		J = [0] * (m + 1)
		for i in range(m):
			J[I[i]] = i + 1
		D = T
		for num in J[1:]:
			if not num in D:
				D[num] = {}
			D = D[num]
		A.append(I)
	Ans2 = []
	for data in A:
		Ans = 0
		D = T
		for num in data:
			if num in D:
				Ans += 1
				D = D[num]
			else:
				break
		Ans2.append(Ans)
	print(*Ans2)


from bisect import bisect

def prefix_len(p, q, m):
	i = 0
	while i < m and p[i] == q[i]:
		i += 1
	return i
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	ps = []
	for _ in range(n):
		p = list(map(int, input().split()))
		ps.append(p)
	qs = []
	for p in ps:
		q = [None] * len(p)
		for (i, x) in enumerate(p, 1):
			q[x - 1] = i
		qs.append(q)
	qs.sort()
	for p in ps:
		idx = bisect(qs, p)
		cnt = 0
		for j in (idx - 1, idx, idx + 1):
			if 0 <= j < n:
				cnt = max(cnt, prefix_len(p, qs[j], m))
		print(cnt, end=' ')
	print()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	t = {}
	y = []
	for _ in range(n):
		z = list(map(int, input().split()))
		q = [0] * (m + 1)
		for i in range(m):
			q[z[i]] = i + 1
		x = t
		for num in q[1:]:
			if not num in x:
				x[num] = {}
			x = x[num]
		y.append(z)
	ans2 = []
	for data in y:
		ans = 0
		x = t
		for num in data:
			if num in x:
				ans += 1
				x = x[num]
			else:
				break
		ans2.append(ans)
	print(*ans2)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	b = [[0] * m for _ in range(n)]
	for i in range(n):
		for j in range(m):
			a[i][j] -= 1
			b[i][a[i][j]] = j
	c = [set() for _ in range(m)]
	for i in range(n):
		h = 0
		for j in range(m):
			h = h * 10 + b[i][j]
			c[j].add(h)
	ans = []
	for i in range(n):
		h = 0
		t = 0
		for j in range(m):
			h = h * 10 + a[i][j]
			if h in c[j]:
				t = j + 1
		ans += (t,)
	print(*ans)


import sys

def make_empty_dict(size):
	return {idx: None for idx in range(1, size + 1)}

def make_tree(rev):
	m = len(rev[0])
	root = make_empty_dict(size=m)
	for perm in rev:
		tmp = root
		for el in perm:
			if tmp[el] is None:
				tmp[el] = make_empty_dict(size=m)
			tmp = tmp[el]
	return root

def search_path(tree, perm):
	lvl = 0
	tmp = tree
	for el in perm:
		if tmp[el] is None:
			break
		else:
			tmp = tmp[el]
			lvl += 1
	return lvl

def solution():
	(n, m) = map(int, input().split())
	data = []
	rev = []
	for _ in range(n):
		data.append(list(map(int, input().split())))
		perm = [0] * m
		for (idx, el) in enumerate(data[-1]):
			perm[el - 1] = idx + 1
		rev.append(perm)
	tree = make_tree(rev)
	ans = [search_path(tree, perm) for perm in data]
	print(*ans)
t = int(input())
for _ in range(t):
	solution()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	all = set()
	for i in range(n):
		prefix = ''
		for j in range(m):
			prefix += str(a[i].index(j + 1) + 1)
			all.add(prefix)
	res = []
	for i in range(n):
		tmp = 0
		prefix = ''
		for j in range(m):
			prefix += str(a[i][j])
			if prefix in all:
				tmp += 1
			else:
				break
		res.append(tmp)
	print(*res)


import sys
input = sys.stdin.readline

class TrieNode:

	def __init__(self, v=None):
		self.children = {}
		self.val = v
		self.end = False

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	(n, m) = readInts()
	arr = [readList() for _ in range(n)]
	root = TrieNode()
	for i in range(n):
		node = root
		inv = [0] * m
		for j in range(m):
			inv[arr[i][j] - 1] = j + 1
		for j in range(m):
			if inv[j] not in node.children:
				node.children[inv[j]] = TrieNode(inv[j])
			node = node.children[inv[j]]
	ans = []
	for i in range(n):
		node = root
		cnt = 0
		for j in range(m):
			if arr[i][j] in node.children:
				node = node.children[arr[i][j]]
				cnt += 1
			else:
				break
		ans.append(cnt)
	return ans
for _ in range(int(input())):
	print(*solve())


def getint():
	return int(input())

def getfloat():
	return float(input())

def getints():
	return list(map(int, input().split()))

def getfloats():
	return list(map(float, input().split()))

class TrieNode:

	def __init__(self):
		self.isWord = False
		self.next = {}

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, word):
		n = self.root
		for i in word:
			if i not in n.next:
				n.next[i] = TrieNode()
			n = n.next[i]
		n.isWord = True

	def search(self, word):
		n = self.root
		ans = 0
		for i in word:
			if i not in n.next:
				return ans
			else:
				ans += 1
				n = n.next[i]
		return ans

def inv(a):
	c = [0 for i in range(len(a))]
	for (i, k) in enumerate(a):
		c[k - 1] = i + 1
	return c
from collections import deque
T = getint()
for _t in range(T):
	(n, m) = getints()
	mat = [getints() for j in range(n)]
	remains = deque(list(range(n)))
	ans = [0 for i in range(n)]
	trie = Trie()
	for m in mat:
		trie.insert(inv(m))
	for i in range(n):
		ans[i] = trie.search(mat[i])
	print(' '.join(map(str, ans)))


import sys
from collections import defaultdict
input = sys.stdin.readline
debug = print if 'LOCAL' in sys.argv else lambda *_: None
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mp = defaultdict(list)
	mx = {}
	a = [[0] * m for _ in range(n)]
	for i in range(n):
		s = ''
		for (j, val) in enumerate(map(int, input().split())):
			a[i][j] = val - 1
			s += str(a[i][j])
			mp[s].append(i)
		debug(a[i])
	for i in range(n):
		p = [0] * m
		for j in range(m):
			p[a[i][j]] = j
		s = ''
		for b in range(1, m + 1):
			s += str(p[b - 1])
			mx[s] = max(mx.get(s, 0), b)
	ans = [0] * n
	for (s, v) in mp.items():
		val = mx.get(s, 0)
		for x in v:
			ans[x] = max(ans[x], val)
	print(*ans)