Королевство Берляндия представляет собой множество из n городов, связанных n - 1 железнодорожными путями. Каждый путь соединяет ровно два различных города. Столица находится в городе номер 1. Из каждого города существует способ доехать по железной дороге до столицы.

В i-ом городе стоит дивизия солдат номер i, каждая дивизия характеризуется числом a_i, означающим приоритет; чем меньше это число, тем выше приоритет у этой дивизии. Все значения a_i — различны.

Однажды Король Берляндии Берл Великий объявил всеобщую мобилизацию, и для этого каждая дивизия должна прибыть в столицу. Каждый день из каждого города, кроме столицы, по каждому железнодорожному пути отходит поезд, который имеет некоторую конечную вместимость c_j, выражаемую в максимальном количестве дивизий, которое этот поезд может увезти за один раз. Каждый поезд двигается по направлению сокращения расстояния до столицы. Поезд заканчивает свой путь на противоположном конце железнодорожного пути на следующий день. Таким образом, каждый поезд проезжает из города в соседний (в которой и заканчивает свой путь) по направлению к столице.

В первую очередь из числа дивизий, находящихся в городе, на поезд садятся дивизии с наименьшим числом a_i, потом со следующим по величине и так далее, пока либо поезд не будет заполнен, либо пока все дивизии не будут погружены. Таким образом, некоторые дивизии могут оставаться в городе в ожидании поезда несколько дней.

Длительность путешествия поезда из одного города в другой всегда равно 1 дню. Все дивизии начинают свое передвижение одновременно и заканчивают в столице, откуда больше никуда не перемещаются. Каждая дивизия передвигается по простому пути из своего города в столицу, независимо от того, сколько времени займет это путешествие.

Ваша задача — найти для каждой дивизии, через сколько дней она прибудет в столицу Берляндии. Отсчет времени начинается с дня номер 0.