Поликарп пригласил \(n\) друзей на встречу Нового года. Во время торжества он решил сделать общую фотографию всех своих друзей. Каждый друг может стоять или лечь на бок.
Каждый друг характеризуется двумя значениями \(h_i\) (его рост) и \(w_i\) (его ширина). На фото \(i\)-й друг будет занимать прямоугольник \(h_i \times w_i\) (если он стоит) или \(w_i \times h_i\) (если он лежит).
Друга с номером \(j\) можно разместить перед \(i\)-м другом на фотографии, если его прямоугольник ниже и уже, чем прямоугольник \(i\)-го друга. Формально должно быть выполнено хотя бы одно из следующих условий:
- \(h_j < h_i\) и \(w_j < w_i\) (оба друга стоят или оба лежат);
- \(w_j < h_i\) и \(h_j < w_i\) (один из друзей стоит, а другой лежит).
Например, если \(n = 3\), \(h=[3,5,3]\) и \(w=[4,4,3]\), то:
- первого друга можно поставить перед вторым: \(w_1 < h_2\) и \(h_1 < w_2\) (один из них стоит, а другой лежит);
- третьего друга можно поставить перед вторым: \(h_3 < h_2\) и \(w_3 < w_2\) (оба друга стоят или оба лежат).
В других случаях человек на переднем плане будет перекрывать человека на заднем плане.
Помогите Поликарпу для каждого \(i\) найти любой \(j\), такой, что перед \(i\)-м другом может быть расположен \(j\)-й друг (т.е. хотя бы одно из условий выше было выполнено).
Обратите внимание, что вам не нужно находить расположение всех людей для общей фотографии. Вам нужно, чтобы каждый друг \(i\) нашел любого другого друга \(j\), который может оказаться перед ним. Думайте об этом, как о решении \(n\) независимых подзадач.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(n\) целых чисел, где \(i\)-е число является номером друга, которого можно поставить перед \(i\)-м. Если такого друга не существует, то выведите -1.
Если существует несколько ответов, выведите любой.
Примечание
Первый набор входных данных разобран в условии.
Во третьем наборе входных данных следующие варианты ответы тоже являются верными:
- \([-1, -1, 1, 2]\);
- \([-1, -1, 1, 1]\);
- \([-1, -1, 2, 1]\).