Circular Permutation Recovery Solution|Codesheff lunchtime 2022 for div 3

You are given to integers N,K$N,K$ such that K+1≤N≤2K−1$K+1\le N\le 2K-1$. Your friend is hiding from you a permutation (P1,P2,…,PN)$(P_1,P_2,\dots ,P_N)$ of integers from 1$1$ to N$N$, whose elements are written cyclically.

Your friend doesn't tell you the permutation. Instead, he tells you this. For each i$i$ from 1$1$ to N$N$ he will tell you Ai$A_i$ −$-$ the number of such integers j$j$ with 0≤j<K$0\le j<K$ such that P((i+j)modN)+1<Pi$P_{((i+j)modN)+1}<P_i$.

Given A1,A2,…,AN$A_1,A_2,\dots ,A_N$, find any permutation P$P$ producing them or tell that there is no such permutation.

Input Format

The first line of the input contains a single integer T$T$ −$-$ the number of test cases. The description of test cases follows.

The first line of each test case contains two integers N,K$N,K$.

The second line of each test case contains N$N$ integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output Format

For each test case, if there is no permutation producing array A$A$, output −1$-1$. Otherwise, output N$N$ integers P1,P2,…,PN$P_1,P_2,\dots ,P_N$ (1≤Pi≤N$1\le P_i\le N$, Pi≠Pj$P_i\ne P_j$ for i≠j$i\ne j$) −$-$ the required permutation. If there are several such permutations, you can output any.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤K+1≤N≤2K−1$1\le K+1\le N\le 2K-1$.
• 0≤Ai≤K$0\le A_i\le K$
• 3≤N≤2⋅105$3\le N\le 2\cdot {10}^5$
• The sum of N$N$ over all test cases doesn't exceed 2⋅105$2\cdot {10}^5$

Subtasks

Subtask 1 (50 points): The sum of N$N$ over all test cases doesn't exceed 2000$2000$ Subtask 2 (50 points): No additional constraints

Sample Input 1 

2
5 3
1 2 1 3 0
5 3
3 0 0 0 1

Sample Output 1 

3 4 2 5 1 
-1

Explanation

In the first test case, (3,4,2,5,1)$(3,4,2,5,1)$ produces A=[1,2,1,3,0]$A=[1,2,1,3,0]$. Indeed, there is one element among 4,2,5$4,2,5$ smaller than 3$3$, there are 2$2$ elements among 2,5,1$2,5,1$ smaller than 4$4$, one element among 5,1,3$5,1,3$ smaller than 2$2$, three elements among 1,3,4$1,3,4$ smaller than 5$5$, and no elements among 3,4,2$3,4,2$ smaller than 1$1$.

It can be shown that array A$A$ from the second test case doesn't correspond to any permutation

Solution:

This question solution is updated within contest time. please click on follow button and subscribe our channel.if you follow and subscribe our channel then get notification of answer as soon as possible.