## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Permutation Restoration Codeforces Solution

D. Permutation Restoration
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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}=⌊\frac{i}{{a}_{i}}⌋$. For example, if the permutation $a$ is $\left[2,1,4,3\right]$, then the array $b$ is equal to $\left[⌊\frac{1}{2}⌋,⌊\frac{2}{1}⌋,⌊\frac{3}{4}⌋,⌊\frac{4}{3}⌋\right]=\left[0,2,0,1\right]$.

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

Solution Click Below:-  👉
👇👇👇👇👇

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}$).

Grass Field Codeforces Solution

Permutation Codeforces Solution

Schedule Management Codeforces Solution

Permutation Restoration Codeforces Solution

Text Editor Codeforces Solution

Points Codeforces Solution

The second line contains $n$ integers ${b}_{1},{b}_{2},\dots ,{b}_{n}$ ($0\le {b}_{i}\le n$).

• 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$.
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.