В погоне за очередным сокровищем капитан Флинт наткнулся на некоторую задачу, которая может быть связана с поиском сокровища, а может и не быть. Поэтому капитан Флинт поручил ее решение своим матросам и назначил огромное вознаграждение: целый один выходной день. Задача же звучит так...
Заданы массивы \(a\) и \(b\) длины \(n\). Изначально, \(ans\) равен \(0\) и определена следующая операция:
- Выбрать позицию \(i\) (\(1 \le i \le n\));
- Добавить к \(ans\) значение \(a_i\);
- Если \(b_i \neq -1\), то добавить к \(a_{b_i}\) значение \(a_i\);
Какой максимальный \(ans\) можно получить, применив эту операцию к каждой позиции \(i\) (\(1 \le i \le n\)) ровно один раз?
Дядя Богдан очень хочет получить вознаграждение и просит Вас помочь ему с решением задачи, а также предоставить порядок позиций, в котором нужно применять операцию выше.
Выходные данные
В первой строке выведите одно целое число, максимальный \(ans\), который можно получить.
Во второй строке опишите последовательность выполнения операций, чтобы получить этот максимальный ответ: \(n\) различных целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)), где \(p_i\) обозначает позицию, операция над которой выполняется \(i\)-й по порядку. Если существует несколько таких последовательностей, выведите любою из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
2 3 -1
|
10
1 2 3
|
|
2
|
2
-1 100
2 -1
|
99
2 1
|
|
3
|
10
-10 -1 2 2 5 -2 -3 -4 2 -6
-1 -1 2 2 -1 5 5 7 7 9
|
-9
3 5 6 1 9 4 10 7 8 2
|