Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

greedy

math

sortings

two pointers

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Permutation Restoration

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMonocarp 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.

Example

Input

440 2 0 121 150 0 1 4 130 1 3

Output

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/24/2024 04:00:25 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|