Masha and Grisha like studying sets of positive integers.

One day Grisha has written a set A containing n different integers a_{i} on a blackboard. Now he asks Masha to create a set B containing n different integers b_{j} such that all n^2 integers that can be obtained by summing up a_{i} and b_{j} for all possible pairs of i and j are different.

Both Masha and Grisha don't like big numbers, so all numbers in A are from 1 to 10^6, and all numbers in B must also be in the same range.

Help Masha to create the set B that satisfies Grisha's requirement.


-----Input-----

Input data contains multiple test cases. The first line contains an integer t — the number of test cases (1 ≤ t ≤ 100).

Each test case is described in the following way: the first line of the description contains one integer n — the number of elements in A (1 ≤ n ≤ 100).

The second line contains n integers a_{i} — the elements of A (1 ≤ a_{i} ≤ 10^6). 


-----Output-----

For each test first print the answer:   NO, if Masha's task is impossible to solve, there is no way to create the required set B.  YES, if there is the way to create the required set. In this case the second line must contain n different positive integers b_{j} — elements of B (1 ≤ b_{j} ≤ 10^6). If there are several possible sets, output any of them. 


-----Example-----
Input
3
3
1 10 100
1
1
2
2 4

Output
YES
1 2 3 
YES
1 
YES
1 2

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Complete search

Constructive algorithms


Solutions:
t = int(input())

def check(arr, v, dic):
	for i in arr:
		if dic[i + v] == 1:
			return True
	return False
dic = [0] * 2000005
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	brr = [1] * n
	cnt = 0
	i = 1
	flag = True
	tmp = {}
	while cnt < n:
		while check(arr, i, dic):
			i += 1
		brr[cnt] = i
		for v in arr:
			dic[i + v] = 1
			tmp[i + v] = 1
		cnt += 1
		i += 1
	if flag:
		print('YES')
		print(' '.join(map(str, brr)))
	else:
		print('NO')
	for k in tmp.keys():
		dic[k] = 0


from random import randint
h = [-1] * 2000001
for t in range(int(input())):
	(n, A) = (int(input()), list(map(int, input().split())))
	B = []
	b = 1
	while len(B) < n:
		b = randint(1, 1000000)
		if all((h[a + b] != t for a in A)):
			for a in A:
				h[a + b] = t
			B.append(b)
	print('YES\n' + ' '.join(map(str, B)))


from random import randint

def solve():
	(n, aa) = (int(input()), list(map(int, input().split())))
	(bb, ab) = (set(), set())
	while True:
		b = randint(1, 1000000)
		for a in aa:
			if a + b in ab:
				break
		else:
			bb.add(b)
			if len(bb) == n:
				break
			for a in aa:
				ab.add(a + b)
	print('YES')
	print(' '.join(map(str, bb)))

def main():
	for _ in range(int(input())):
		solve()
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = []
	b.append(1)
	used = [0] * (10 ** 6 + 1)
	used[1] = 1
	can_be = 2
	diffs = []
	for i in range(n):
		for j in range(i + 1, n):
			diffs.append(a[j] - a[i])
	for i in range(1, n):
		for j in diffs:
			used[min(b[i - 1] + j, 10 ** 6)] = 1
		while used[can_be]:
			can_be += 1
		b.append(can_be)
		used[can_be] = 1
	if len(b) == n:
		print('YES')
		for i in b:
			print(i, end=' ')
		print('')
	else:
		print('NO')


T = int(input())
while T:
	(n, a, bd) = (int(input()), sorted(list(map(int, input().split()))), [0] * 1000001)
	for i in range(n):
		for j in range(i + 1, n):
			bd[a[j] - a[i]] = 1
	i = 1
	while any((bd[i * j] for j in range(1, n))):
		i += 1
	print('YES\n' + ' '.join((str(i * j + 1) for j in range(n))))
	T -= 1


t = int(input())

def check(arr, v, dic):
	for i in arr:
		if dic[i + v] == 1:
			return True
	return False

def check2(arr, v, dic):
	ok = False
	for i in arr:
		if dic[i + v] == 1:
			ok = True
			break
	return ok

def check3(arr, v, dic):
	return any((dic[a + v] == 1 for a in arr))
dic = [0] * 2000005
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	brr = [1] * n
	cnt = 0
	i = 1
	flag = True
	tmp = {}
	while cnt < n:
		ok = True
		for a in arr:
			if dic[a + i] == 1:
				ok = False
				break
		if not ok:
			i += 1
			continue
		for a in arr:
			dic[a + i] = 1
			tmp[a + i] = 1
		brr[cnt] = i
		cnt += 1
		i += 1
	if flag:
		print('YES')
		print(' '.join(map(str, brr)))
	else:
		print('NO')
	for k in list(tmp.keys()):
		dic[k] = 0


d = [-1] * 1000001
for t in range(int(input())):
	(n, a) = (int(input()), list(map(int, input().split())))
	a.sort()
	for i in range(n):
		for j in range(i + 1, n):
			d[a[j] - a[i]] = t
	i = 1
	while any((d[i * j] == t for j in range(1, n))):
		i += 1
	print('YES\n' + ' '.join((str(j * i + 1) for j in range(n))))


visited = [-1] * (2 * 10 ** 6 + 1)
t = int(input())
for i in range(t):
	(n, A) = (int(input()), list(map(int, input().split())))
	A.sort()
	res = []
	v = 1
	while len(res) < n:
		flag = True
		for a in A:
			if visited[a + v] == i:
				flag = False
				break
		if not flag:
			v += 1
			continue
		for a in A:
			visited[a + v] = i
		res.append(v)
		v += 1
	print('YES\n' + ' '.join(map(str, res)))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	ab = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			ab = ab * x % p
		y = y >> 1
		x = x * x % p
	return ab

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return [int(x) for x in input().split()]
bb = [-1] * 2000009
t = int(input())
for j in range(t):
	n = int(input())
	a = mapin()
	a.sort()
	ab = []
	v = 1
	while len(ab) < n:
		fl = True
		for i in a:
			if bb[i + v] == j:
				fl = False
				break
		if not fl:
			v += 1
			continue
		for i in a:
			bb[i + v] = j
		ab.append(v)
		v += 1
	print('YES')
	print(*ab)


from random import randint
visited = [-1] * (2 * 10 ** 6 + 1)
t = int(input())
for i in range(t):
	(n, A) = (int(input()), list(map(int, input().split())))
	res = []
	while len(res) < n:
		v = randint(1, 10 ** 6)
		if all((visited[a + v] != i for a in A)):
			for a in A:
				visited[a + v] = i
			res.append(v)
	print('YES\n' + ' '.join(map(str, res)))