Художники по керамике Мария и Жоао открывают небольшой магазин азулежу в Порту. Азулежу - красивая керамическая плитка, которой славится Португалия. Мария и Жоао хотят создать привлекательную витрину, но из-за ограниченного пространства в их магазине им приходится размещать образцы плитки в два ряда на одной полке. Перед каждой плиткой Жоао находится ровно одна плитка Марии, а за каждой плиткой Марии находится ровно одна плитка Жуана. Эти плитки ручной работы бывают самых разных размеров, и важно, чтобы каждая плитка в заднем ряду была выше, чем плитка перед ней, чтобы обе были видны прохожим. Для удобства покупателей плитки в каждом ряду расположены в порядке неубывания цены слева направо. Плитки одной цены могут располагаться в любом порядке при условии соблюдения условий видимости, указанных выше.
Ваша задача - найти порядок плиток в каждой строке, удовлетворяющий этим ограничениям, или определить, что такого порядка не существует.
Первая строка содержит целое число n (1 ≤ n ≤ 5 * 10^5
) - количество плиток в каждой строке. Следующие четыре строки содержат по n целых чисел в каждой; первая пара строк представляет задний ряд плиток, вторая пара строк представляет передний ряд. Плитки в каждой строке пронумерованы от 1 до n в соответствии с их порядком во входных данных. Первая строка в каждой паре содержит n целых чисел p[1]
, ..., p[n]
(1 ≤ p[i]
≤ 10^9
для каждый i), где p[i]
- цена плитки номер i в этой строке. Вторая строка в каждой паре содержит n целых чисел h[1]
, ..., h[n]
(1 ≤ h[i]
≤ 10^9
для каждый i), где h[i]
- высота плитки с номером i в этой строке.
Если существует допустимый порядок, выведите его в виде двух строк из n целых чисел, каждая из которых состоит из перестановки номеров плиток от 1 до n. Первая строка представляет порядок плиток в заднем ряду, а вторая - порядок плиток в переднем ряду. Если больше одной пары перестановок удовлетворяет ограничениям, выведите любую. Если требуемого порядка не существует, выведите impossible.