Your task is to find an ordering of the tiles in each row that satisfies these constraints, or determine that no such ordering exists.
The first line of input contains an integer $n$ ($1 \leq n \leq 5\cdot 10^5$), the number of tiles in each row. The next four lines contain $n$ integers each; the first pair of lines represents the back row of tiles and the second pair of lines represents the front row. Tiles in each row are numbered from $1$ to $n$ according to their ordering in the input. The first line in each pair contains $n$ integers $p_1, \ldots , p_ n$ ($1 \leq p_ i \leq 10^9$ for each $i$), where $p_ i$ is the price of tile number $i$ in that row. The second line in each pair contains $n$ integers $h_1, \ldots , h_ n$ ($1 \leq h_ i \leq 10^9$ for each $i$), where $h_ i$ is the height of tile number $i$ in that row.
If there is a valid ordering, output it as two lines of $n$ integers, each consisting of a permutation of the tile numbers from $1$ to $n$. The first line represents the ordering of the tiles in the back row and the second represents the ordering of the tiles in the front row. If more than one pair of permutations satisfies the constraints, any such pair will be accepted. If no ordering exists, output impossible.
Sample Input 1 | Sample Output 1 |
---|---|
4 3 2 1 2 2 3 4 3 2 1 2 1 2 2 1 3 |
3 2 4 1 4 2 1 3 |
Sample Input 2 | Sample Output 2 |
---|---|
2 1 2 2 3 2 8 2 1 |
impossible |