Програмчлалын үндсэн аргууд

n натурал тоо болон a₁, ..., a_n бодит тоонууд өгөгдөв (a_i≠0, i=1, ..., n). a_i, a_i+1, a_i+2 гурван тоо бүрийн (i=1, 2, ..., n-2) тэмдгүүдийн дараалал нь +++, ++-, +-+, +--, -++, -+-, --+, --- гэсэн хослолуудын аль нэг байж болно. Дээрх хослолууд a₁, ..., a_n дараалалд хэд байгааг илэрхийлэх b₀, ..., b₇ бүхэл тоон дарааллыг байгуул.

Input

n натурал тоо болон a₁, ..., a_n бодит тоонууд (n <= 3*10⁵, |a_i|<=2³¹)

Output

b₀, ..., b₇ бүхэл тоонууд

Example

Input:
4
1031127592.0
-2039255727.0
-1702370466.0
1776528990.0

Output:
0
0
0
1
0
0
1
0