Monocarp had a permutation $a$ of $n$ integers $1$, $2$, ..., $n$ (a permutation is an array where each element from $1$ to $n$ occurs exactly once).

Then Monocarp calculated an array of integers $b$ of size $n$, where $b_i = \left\lfloor \frac{i}{a_i} \right\rfloor$. For example, if the permutation $a$ is $[2, 1, 4, 3]$, then the array $b$ is equal to $\left[ \left\lfloor \frac{1}{2} \right\rfloor, \left\lfloor \frac{2}{1} \right\rfloor, \left\lfloor \frac{3}{4} \right\rfloor, \left\lfloor \frac{4}{3} \right\rfloor \right] = [0, 2, 0, 1]$.

Unfortunately, the Monocarp has lost his permutation, so he wants to restore it. Your task is to find a permutation $a$ that corresponds to the given array $b$. If there are multiple possible permutations, then print any of them. The tests are constructed in such a way that least one suitable permutation exists.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^5$) — number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le n$).

Additional constrains on the input:

the sum of $n$ over test cases does not exceed $5 \cdot 10^5$;

there exists at least one permutation $a$ that would yield this array $b$.


-----Output-----

For each test case, print $n$ integers — a permutation $a$ that corresponds to the given array $b$. If there are multiple possible permutations, then print any of them.


-----Examples-----

Input
4
4
0 2 0 1
2
1 1
5
0 0 1 4 1
3
0 1 3
Output
2 1 4 3 
1 2 
3 4 2 1 5 
3 2 1


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Sorting

Amortized analysis

Greedy algorithms

Mathematics

Data structures


Solutions:
import heapq

def solve(arr):
	ranges_begin = [[] for _ in range(len(arr) + 1)]
	for j in range(len(arr)):
		val = arr[j]
		i = j + 1
		if val == 0:
			min_real = i + 1
			max_real = len(arr)
		else:
			max_real = i // val
			if i % (val + 1) == 0:
				min_real = i // (val + 1) + 1
			else:
				min_real = i // (val + 1) + 1
		ranges_begin[max_real].append((-min_real, j))
	res = [0 for _ in range(len(arr))]
	my_heap = []
	for val in range(len(arr), 0, -1):
		for r in ranges_begin[val]:
			heapq.heappush(my_heap, r)
		mini_of_heap = heapq.heappop(my_heap)
		res[mini_of_heap[1]] = val
	return res
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	res_arr = solve(arr)
	print(' '.join(map(str, res_arr)))


import sys
import heapq
input = sys.stdin.readline

def solve():
	n = int(input())
	B = list(map(int, input().split()))
	intervals = [[] for _ in range(n + 1)]
	heads = []
	for i in range(n):
		f = (i + 1) // (B[i] + 1) + 1
		b = (i + 1) // B[i] if B[i] else n
		heapq.heappush(intervals[f], (b, i))
	cnt = 1
	ans = [0] * n
	while cnt <= n:
		if intervals[cnt]:
			if heads and intervals[cnt][0][0] > heads[0][0]:
				ans[heapq.heappop(heads)[-1]] = cnt
			else:
				ans[heapq.heappop(intervals[cnt])[-1]] = cnt
			while intervals[cnt]:
				heapq.heappush(heads, heapq.heappop(intervals[cnt]))
		else:
			ans[heapq.heappop(heads)[-1]] = cnt
		cnt += 1
	return ans
for _ in range(int(input())):
	print(*solve())


import heapq
for _ in range(int(input())):
	n = int(input())
	b = map(int, input().split())
	u = sorted((((i + 1) // (x + 1), n if x == 0 else (i + 1) // x, i) for (i, x) in enumerate(b)))
	a = [0] * n
	heap = []
	j = 0
	for i in range(n):
		while j < n and u[j][0] <= i:
			heapq.heappush(heap, u[j][1:])
			j += 1
		a[heapq.heappop(heap)[1]] = i + 1
	print(*a)


import heapq
for _ in range(int(input())):
	N = int(input())
	Arr = list(map(int, input().split()))
	ranges_begin = [[] for i in range(N + 1)]
	for j in range(N):
		val = Arr[j]
		i = j + 1
		min_real = i + 1 if val == 0 else i // (val + 1) + 1
		max_real = N if val == 0 else i // val
		ranges_begin[max_real].append((-min_real, j))
	answer = [0] * N
	my_heap = []
	for val in range(N, 0, -1):
		for r in ranges_begin[val]:
			heapq.heappush(my_heap, r)
		mini_of_heap = heapq.heappop(my_heap)
		answer[mini_of_heap[1]] = val
	print(*answer)


import heapq
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = sorted((((i + 1) // (x + 1), N if x == 0 else (i + 1) // x, i) for (i, x) in enumerate(A)))
	answer = [0] * N
	heap = []
	j = 0
	for i in range(N):
		while j < N and B[j][0] <= i:
			heapq.heappush(heap, B[j][1:])
			j += 1
		answer[heapq.heappop(heap)[1]] = i + 1
	print(*answer)


import sys
import collections

def maximum(a, b):
	return max(a, b)

def minimum(a, b):
	return min(a, b)

def leftshift(a):
	return a << 1

def INPUT():
	return int(input())

def GINPUT():
	return input()

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

def LIST_INPUT():
	return list(map(int, input().split()))
import sys
input = sys.stdin.readline
from heapq import heappush, heappop, heappushpop, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	L = []
	for i in range(n):
		l = (i + 1) // (b[i] + 1) + 1
		if b[i] == 0:
			r = n
		else:
			r = (i + 1) // b[i]
		L.append((l, r, i + 1))
	L.sort()
	ans = [0] * n
	l = []
	idx = 0
	for i in range(1, n + 1):
		while idx < n and L[idx][0] <= i:
			heappush(l, (L[idx][1], L[idx][2]))
			idx += 1
		(x, y) = heappop(l)
		ans[y - 1] = i
	print(*ans)


import queue
import sys, math
import heapq
from collections import deque
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
pop = heapq.heappop
push = heapq.heappush

def ip():
	return int(input())

def sp():
	return str(input().rstrip())

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

def msp():
	return map(str, input().split())

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

def lmsp():
	return list(map(str, input().split()))
for tcs in range(int(input())):
	n = ip()
	b = [0] + [int(x) for x in input().split()]
	a = []
	for i in range(1, n + 1):
		if b[i] == 0:
			a.append([i + 1, n, i])
		else:
			a.append([i // (b[i] + 1) + 1, i // b[i], i])
	a.sort(key=lambda x: (x[0], -x[1]))
	pq = []
	ans = [0] * n
	now = 1
	i = 0
	f = 0
	for f in range(n):
		while i < n and a[i][0] <= now <= a[i][1]:
			push(pq, [a[i][1], a[i][2]])
			i += 1
		g = pop(pq)
		ans[g[1] - 1] = now
		now += 1
	print(*ans)


from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))
import heapq

def answer():
	start = [[] for i in range(n + 2)]
	end = [[] for i in range(n + 2)]
	for i in range(n):
		l = (i + 1) // (b[i] + 1)
		if b[i]:
			r = (i + 1) // b[i]
		else:
			r = n
		start[l + 1].append([r, i])
		end[r].append([r, i])
	ans = [-1 for i in range(n)]
	(take, done) = ([], dict())
	for i in range(1, n + 1):
		for x in start[i]:
			heapq.heappush(take, x)
		x = heapq.heappop(take)
		while done.get(tuple(x), False):
			x = heapq.heappop(take)
		ans[x[1]] = i
		for x in end[i]:
			done[tuple(x)] = True
	return ans
for T in range(int(input())):
	n = int(input())
	b = inp()
	print(*answer())