AT_arc209_d [ARC209D] A_A_i

You are given a sequence $ A = (A_1, A_2, \ldots, A_N) $ of length $ N $ . Each element is either an integer between $ 1 $ and $ N $ (inclusive) or $ -1 $ . Snuke has decided to create a new sequence using this sequence $ A $ . First, replace all $ -1 $ s in this sequence $ A $ with integers between $ 1 $ and $ N $ (inclusive). Next, create a sequence $ B = (B_1, B_2, \ldots, B_N) $ of length $ N $ according to the following formula: - $ B_i=A_{A_i} $ Find the lexicographically smallest possible sequence $ B $ . You are given $ T $ test cases. Solve each of them. What is the lexicographical order of sequences?A sequence $ C = (C_1,C_2,\ldots,C_N) $ is **lexicographically smaller** than a sequence $ D = (D_1,D_2,\ldots,D_N) $ if and only if there exists an integer $ 1 \leq i \leq N $ such that both of the following hold: - $ (C_1,C_2,\ldots,C_{i-1}) = (D_1,D_2,\ldots,D_{i-1}) $ - $ C_i $ is (numerically) smaller than $ D_i $ .

The input is given from Standard Input in the following format: > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ Each case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

For each test case, output the lexicographically smallest possible sequence $ B $ , separated by newlines.

### Sample Explanation 1 In the first test case, the sequence $ A $ before Snuke's replacement is $ (4,-1,-1,3) $ . Suppose he replaces it to get $ A=(4, 3, 1, 3) $ . Then, $ B=(A_4, A_3, A_1, A_3)=(3, 1, 4, 1) $ . It is impossible to obtain a lexicographically smaller sequence $ B $ than this. ### Constraints - $ 1 \le T \le 10^5 $ - $ 1 \le N \le 5 \times 10^5 $ - $ 1 \le A_i \le N $ or $ A_i = -1 $ . - The sum of $ N $ over all test cases is at most $ 5\times 10^5 $ . - All input values are integers.