Вы владелец зверинца, состоящего из \(n\) животных пронумерованных от \(1\) до \(n\). Однако содержать зверинец достаточно затратно, поэтому вы решили его продать!
Известно, что каждое животное боится ровно одного другого животного. А точнее, животное \(i\) боится животного \(a_i\) (\(a_i \neq i\)). Также для каждого животного известна его стоимость, для животного \(i\) она равняется \(c_i\).
Вы будете продавать всех своих животных в каком-то зафиксированном порядке. Формально, вам надо будет выбрать некоторую перестановку\(^\dagger\) \(p_1, p_2, \ldots, p_n\), и продать сначала животное \(p_1\), потом животное \(p_2\), и так далее, последним продав животное \(p_n\).
Когда вы продаёте животное \(i\), есть два варианта развития событий:
- Если животное \(a_i\) было продано раньше чем животное \(i\), вы получаете \(c_i\) денег за продажу животного \(i\).
- Если животное \(a_i\) не было продано раньше чем животное \(i\), вы получаете \(2 \cdot c_i\) денег за продажу животного \(i\). (Удивительно, но животные, которые боятся в текущий момент имеют большую ценность).
Ваша задача — выбрать порядок продажи животных так, чтобы максимизировать суммарную прибыль.
Например, если \(a = [3, 4, 4, 1, 3]\), \(c = [3, 4, 5, 6, 7]\) и выбранная вами перестановка равна \([4, 2, 5, 1, 3]\), то:
- Первым продаётся животное \(4\). Животное \(a_4 = 1\) не было продано ранее, а значит, вы получаете \(2 \cdot c_4 = 12\) денег за продажу.
- Вторым продаётся животное \(2\). Животное \(a_2 = 4\) было продано ранее, а значит, вы получаете \(c_2 = 4\) денег за продажу.
- Третьим продаётся животное \(5\). Животное \(a_5 = 3\) не было продано ранее, а значит, вы получаете \(2 \cdot c_5 = 14\) денег за продажу.
- Четвёртым продаётся животное \(1\). Животное \(a_1 = 3\) не было продано ранее, а значит, вы получаете \(2 \cdot c_1 = 6\) денег за продажу.
- Пятым продаётся животное \(3\). Животное \(a_3 = 4\) было продано ранее, а значит, вы получаете \(c_3 = 5\) денег за продажу.
Ваша суммарная прибыль при таком выборе перестановки, равна \(12 + 4 + 14 + 6 + 5 = 41\). Обратите внимание, что \(41\) — не максимально возможная прибыль в этом примере.
\(^\dagger\) Перестановкой длины \(n\) называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но в массиве присутствует \(4\)).
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите \(n\) целых чисел — перестановку \(p_1, p_2, \ldots, p_n\), обозначающую, в каком порядке нужно продавать животных, чтобы максимизировать прибыль. Если есть несколько возможных ответов, можно вывести любой из них.