Однажды, во время своего путешествия, Фрирен наткнулась на магазин гримуаров, и как можно догадаться, купила $$$n$$$ гримуаров, потратив на это почти все свои сбережения. Придя домой, Фрирен поверхностно изучила каждый из них, и охарактеризовала $$$i$$$-й гримуар двумя параметрами $$$a_i$$$ (сложность) и $$$b_i$$$ (потенциал).
Так как Фрирен никуда не торопится, при изучении для нее интересен не только потенциал полученных знаний, но и удовольствие от разбора сложных гримуаров. Поэтому она решила, что будет изучать гримуары в особом порядке. Если ей скучно, она будет изучать самый сложный гримуар (с максимальным $$$a_i$$$) из всех доступных; а если она почувствует, что ей хочется узнать что-то совершенно новое, она выберет гримуар с самым большим потенциалом $$$b_i$$$.
Если есть несколько гримуаров с максимальным интересующим Фрирен параметром, то она выберет тот из них, у которого максимален второй параметр, а если и вторые параметры равны, то Фрирен возьмет тот из них, который она купила раньше.
Фрирен будет выбирать книги по настроению и, очевидно, не будет заново изучать уже прочитанный гримуар. Поэтому Ферн планирует уже изученные гримуары продавать, чтобы хоть немного восстановить денежные ресурсы команды. Но, чтобы случайно не продать еще не изученный гримуар, она просит вас вывести, в каком порядке Фрирен будет их читать.
В первой строке ввода дано целое число $$$n$$$ — количество купленных гримуаров ($$$1 \le n \le 10^5$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — значения сложности гримуаров в порядке их покупки ($$$1 \le a_i \le 10^9$$$). В третьей строке в том же формате даны целые числа $$$b_i$$$ — значения потенциалов гримуаров ($$$1 \le b_i \le 10^9$$$).
В последней строке через пробел перечислены $$$n$$$ целых чисел $$$p_i$$$ — индикаторы настроения Фрирен перед выбором $$$i$$$-го гримуара. Если $$$p_i = 1$$$, Фрирен будет выбирать гримуар с максимальным потенциалом, иначе $$$p_i = 0$$$ и Фрирен выберет самый сложный из доступных гримуаров.
Выведите $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$, разделенных пробелами; $$$i$$$-е число должно быть равно номеру гримуара, который выберет Фрирен в $$$i$$$-й раз.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
1 | 10 | $$$n, a_i, b_i \le 10$$$ | полная | |
2 | 5 | все $$$a_i$$$ одинаковы | первая ошибка | |
3 | 10 | $$$1 \le a_i, b_i \leq n$$$, $$$a_i \ne a_j$$$ и $$$b_i \ne b_j$$$ для всех $$$i \ne j$$$ | первая ошибка | |
4 | 30 | $$$n \le 1000$$$ | 1 | первая ошибка |
5 | 5 | для любых $$$i \ne j$$$ пары $$$(a_i, b_i)$$$ и $$$(a_j, b_j)$$$ различны | 3 | первая ошибка |
6 | 40 | без дополнительных ограничений | 1 – 5 | первая ошибка |
51 2 3 4 55 4 3 2 11 0 1 0 0
1 5 2 4 3
63 10 6 2 10 13 5 10 7 5 90 0 1 1 0 1
2 5 3 6 1 4