В Т-Поколении очень долгие занятия. За один день надо успеть разобрать тренировочный и тематический тур, прочитать лекцию с новым материалом, а если получится, то еще и провести мини-семинар. Поэтому предусмотрен перерыв, где школьники могут уйти попить кофе и пообщаться между собой.
Всего есть \(n+2\) кофемашины, которые находятся в последовательно расположенных комнатах вдоль длинного коридора. Кофемашины пронумерованы числами от \(0\) до \(n+1\), при чем сразу после начала перерыва у \(i\)-й кофемашины собралось \(a_i\) школьников.
Школьники слишком громко общаются между собой, а преподавателям надо сделать очень важное объявление. Поэтому они хотят собрать наибольшее количество школьников около какой-нибудь одной кофемашины. Преподавателям слишком лениво бегать по коридорам и собирать школьников, поэтому они придумали более изощренный способ ими манипулировать:
- В любой момент преподаватели могут выбрать комнату \(i\) (\(1 \le i \le n\)) и выключить там свет;
- Если в этой комнате находилось \(x\) учеников, тогда после выключения света \(\lfloor \frac12 x \rfloor\) учеников отправятся в комнату \((i-1)\), а \(\lfloor \frac12 x \rfloor\) других школьников отправятся в комнату \((i+1)\).
- Если \(x\) было нечетным, то один школьник остается в той же комнате.
- После этого свет в комнате \(i\) включается обратно.
Преподаватели еще не решили, где они будут собирать школьников, а поэтому для каждого \(i\) от \(1\) до \(n\) вам следует определить, какое наибольшее количество школьников можно собрать около \(i\)-й кофемашины.
Преподаватели могут выключать свет в любых комнатах на свое усмотрение, в любом порядке, возможно, выключая свет в одной и той же комнате несколько раз.
Обратите внимание, что значения \(a_0\) и \(a_{n+1}\) никак не влияют на ответ в задаче, поэтому их значения вам даны не будут.
Выходные данные
Для каждого набора входных данных выведите \(n\) чисел \(b_1, \ldots, b_n\), где \(b_i\) равно наибольшему количеству школьников, которое может оказаться у кофемашины с номером \(i\).