题目描述

课代表在老师的监控下明目张胆的腐败，由于断网了，她只好去玩扫雷了。扫雷对于课代表来说太难了，她让法儿把扫雷的程序改了改，但是……

这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图：

由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案，及输出方案给课代表。

输入格式

第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

输出格式

两行。第一行，即第一列中雷的摆放方案数。 第二行，输出按字典序输出方案，0表示不放雷，1表示放雷。

样例

样例输入

2
1 1

样例输出

2
0 1
1 0

样例解释

方案一：第一行不放雷，第二行放雷

方案二：第一行放雷，第二行不放雷

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$512000\mathrm{KB}$

大样例下载