问题描述

现有 $n$ 个方程组成的线性方程组，格式如下：

$x_1+x_2=a_1$

$x_1+x_2+x_3=a_2$

$x_2+x_3+x_4=a_3$

$\dots \dots\dots$

$x_{n-3}+x_{n-2}+x_{n-1}=a_{n-2}$

$x_{n-2}+x_{n-1}+x_{n}=a_{n-1}$

$x_{n-1}+x_n=a_n$

现在给定你 $a_i(1\le i\le n)$，已知 $x_i$ 由 $0$ 和 $1$ 构成，现在要求你求出该线性方程组的解。由于答案可能不唯一，所以你需要输出字典序最小的一组解。

数据保证该线性方程组至少存在一组解，且一定是合法数据。

输入格式

第一行输入包含一个正整数 $n$，表示线性方程组的数量。（$2\le n\le 2\times 10^5$）。

第二行输入 $n$ 个正整数，第 $i$ 个非负整数表示 $a_i$ 。（$1\le i\le n,0\le a_i\le 3$）。

输出格式

输出 $n$ 个整数，为字典序最小的线性方程组的解，第 $i$ 个整数表示 $x_i$。（$1\le i\le n,0\le x_i\le 1$）。

样例输入

5
1 2 2 2 1

样例输出

0 1 1 0 1

说明

样例解释

该线性方程组有两组解，第一组解为 $\text{0 1 1 0 1}$，第二组解为 $\text{1 0 1 1 0}$，你需要输出第一组解。