Problem description

Bitold jest znany na swoim osiedlu jako właściciel wyjątkowo zadbanego ogrodu. Jego dumą i radością jest elegancki rząd tui, które tworzą gęsty, równiutki żywopłot. Najważniejsze dla Bitolda jest, aby każda tuja miała identyczną wysokość, co nadaje ogrodowi harmonijny wygląd. Niestety, sąsiad Bitolda, Karol, pełen zazdrości, pewnej nocy zakradł się do ogrodu i przyciął niektóre tuje, czyniąc je nierównymi i zdeformowanymi. Bitold nie zamierzał się poddać. W ramach zemsty i z nieugiętą determinacją postanowił jak najszybciej przywrócić swoim tujom jednakową wysokość. Sięgnął po tajną broń – nawóz firmy ByteGarden, który jest znany ze swojej niezwykłej skuteczności. Rozsypanie garści nawozu pod daną tują sprawia, że jej wysokość zwiększa się o 2, a wysokość sąsiadujących z nią tui zwiększa się o 1. Nie chcąc marnować nawozu, Bitold będzie go rozsypywał tylko pod tujami sąsiadującymi z dwoma innymi (nie będącymi na początku lub końcu rzędu). Twoim zadaniem jest pomóc Bitoldowi przywrócić równą wysokość wszystkich tui, zużywając jak najmniej nawozu. Opracuj plan, który wskaże, ile garści nawozu powinien rozsypać pod każdą z tui, aby żywopłot znów był idealnie równy i ogród odzyskał swój dawny blask. Spraw, by ogród Bitolda znów stał się najpiękniejszym miejscem na osiedlu, a zazdrość Karola obróciła się przeciwko niemu.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca liczbę tui tworzących żywopłot. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych T_i, pooddzielanych pojedynczymi odstępami, gdzie T_i określa wysokość i–tej tui w rzędzie, po przycięciu.

Wyjście

W jedynym wierszu wyjścia należy wypisać ciąg N liczb naturalnych A_i, gdzie A_i oznacza liczbę garści nawozu, które należy rozsypać pod i–tą tują. Ciąg powinien zaczynać się i kończyć zerem. Jeżeli rozwiązanie nie istnieje, zamiast tego należy wypisać tylko jedno słowo NIE.

Ograniczenia

5 ≤ N ≤ 1 000 000, 0 ≤ T_i ≤ 1 000 000.

Przykład

6
2 0 1 2 3 4

0 2 0 1 0 0 

5
7 5 6 3 5

NIE