190. Теория вознаграждений

В крупной компании многоуровневая структура. Есть отделения компании, каждое из которых состоит из своих подотделений. В свою очередь каждое подотделение тоже является отделом и может иметь свои подотделения. Известно, что 0-й отдел представляет собой всю компанию целиком.

Каждые полгода происходит оценка эффективности отделов. Исходя из эффективности, которая представляется некоторым числом $a_i$, будет распределено финансирование.

Финансирование происходит следующим образом. Главный 0-й отдел получает $x$ млн.рублей. Среди всех его непосредственных подотделений деньги распределяются пропорционально оценкам (каждое из отделений старается максимально профинансировать свои подотделения). Компания не хочет слишком дробить финансирование, поэтому каждое отделение должно получить целое число млн(это может быть 0). Деньги, которые не распределили по подотделениям, остаются в отделеении и будут направлены в будущем на увеличение финансирования каких-либо проектов отделения. В свою очередь, каждое из этих подотделений проделывает те же самые операции со своими прямыми подотделениями, распределяя между ними деньги.

Так как рассчитывать, сколько денег получит в итоге каждое отделение, — важная и сложная задача, вас попросили написать программу, которая по структуре компании, текущим оценкам эффективности и сумме, которая будет получена 0-ым отделом, выведет финансирование, полученное каждым из отделений.

В первой строке содержится два числа $\,$ — $\, \, n$ $(1 \le n \le 10^5)$ и $m$ $(1 \le m \le 10^{18})\,$ — $\,$количество отделений(не считая 0-й отдел) и количество денег выделенных 0-ым отделом соответственно. В следующей строке содержится ровно n чисел оценки эффективности ($1 \le a_i \le 10^9$). В третьей и последней строке содержится ровно n чисел ($0 \le b_i \le n$), где $b_i$ — номер отдела для которого $i$ отделение является подотделением. Заметим что 0-го отдела нет в списке, следовательно, $ 1 \le i \le n$.

В единственной строке выведите $n$ целых чисел. Где $i$-ое число будет обозначать сколько получило $i$-ое отделение.

В первом примере у 0-го отдела есть 2 подотделения. У первого по результатам оценка эффективности 4, а у второго — 2. Это значит, что количество денег, которые получит первое отделение должно быть в два раза больше.

Так как нулевой отдел выделил лишь 3 млн, первому подотделению достается 2 млн, а второму — 1 млн.

Заметим, что ничего не поменялось бы, если бы 0-й отдел выделил 4 млн. Просто 1 млн остался бы у нулевого.

У второго подотделения нет подотделений, и все деньги останутся у него. У первого подотделения есть два подотделения, оба из которых имеют одинаковые оценки эффективности. Следовательно, деньги делятся между ними поровну — каждому по 1 млн. При этом, несмотря на то, что 1-е отделение перераспределило свои ресурсы, оно получило 2 млн. Следовательно, в ответе для него должно быть выведено 2.

Для лучшего понимания предлагаем взглянуть на картинку, соответствующую первому примеру.