Distance to Next Taller Building

You are given a sequence of building heights. For each building, you are required to compute two values:

1. The distance to the next taller building on its left.
2. The distance to the next taller building on its right.

If there is no taller building in a given direction, output -1 for that direction.

Formally, for each building at index \(i\) with height \(h_i\), define its left distance \(d^L_i\) as: \[ d^L_i = \begin{cases} -1, & \text{if there is no } j h_i, \\ i - j, & \text{where } j \text{ is the largest index less than } i \text{ such that } h_j > h_i. \end{cases} \] Similarly, the right distance \(d^R_i\) is defined as: \[ d^R_i = \begin{cases} -1, & \text{if there is no } j > i \text{ with } h_j > h_i, \\ j - i, & \text{where } j \text{ is the smallest index greater than } i \text{ such that } h_j > h_i. \end{cases} \]

Your task is to process multiple test cases. For each case, compute and output two lines: the first line contains the left distances for all buildings, and the second line contains the right distances.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N_1
h_{1,1} h_{1,2} ... h_{1,N_1}
N_2
h_{2,1} h_{2,2} ... h_{2,N_2}
...
N_T
h_{T,1} h_{T,2} ... h_{T,N_T}

Here, T is the number of test cases. For each test case, the first integer is the number of buildings N, followed by a line containing N space-separated integers representing the heights.

outputFormat

For each test case, output two lines:

• The first line contains the left distances (space-separated).
• The second line contains the right distances (space-separated).

All output is written to standard output (stdout).

## sample

2
6
7 2 8 4 9 1
5
5 5 5 5 5

-1 1 -1 1 -1 1
2 1 2 1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1