Azulejos#11344
Ceramic artists Maria and João are opening a small azulejo shop in Porto. Azulejo is a beautiful ceramic tile for which Portugal is famous. Maria and João want to create an attractive shop window, but due to limited space in their store, they have to place tile samples in two rows on one shelf. In front of each tile of João, there is exactly one tile of Maria, and behind each tile of Maria, there is exactly one tile of João. These handmade tiles come in various sizes, and it is important that each tile in the back row is taller than the tile in front of it so that both are clearly visible to passersby. For the convenience of customers, tiles in each row are arranged in non-decreasing order of price from left to right. Tiles with the same price may be arranged in any order as long as the above visibility requirements are met.
Your task is to find an arrangement of tiles in each row that satisfies these constraints, or determine that no such arrangement exists.
The first line contains an integer (1 \le n \le 5 \cdot 10^5) — the number of tiles in each row.
The next four lines each contain integers: the first two lines describe the back row of tiles, the following two lines describe the front row. Tiles in each line are numbered from to according to their order in the input.
The first line of each pair contains numbers p_1, \ldots, p_n (1 \le p_i \le 10^9) — the prices of the tiles in the respective row.
The second line of each pair contains numbers h_1, \ldots, h_n (1 \le h_i \le 10^9) — the heights of the tiles with the corresponding numbers.
If a valid arrangement exists, print two lines each containing integers — permutations of the tile indices from to .
The first line should specify the order of tiles in the back row, the second line — the order of tiles in the front row.
If there are multiple valid arrangements, print any one of them.
If no valid arrangement exists, print impossible.
Example 1
Example 2