1194 : 黑白跳棋

Description

黑白跳棋是一款在4x4的棋盘上进行的双人游戏，一共有8枚棋子，棋子的一面是黑色，另一面是白色.

如下图所示，游戏开始时双方对坐，棋盘位于中央，黑方将4枚棋子黑面朝上、白方将4枚棋子白面朝上放置在棋盘两端.

通过猜拳确定好先后顺序，双方轮流移动自己的棋子，如果跳过对方的棋子就能把它翻转过来变为己方的棋子.

先把对方棋子全部变成己方棋子的一方获胜，或者不能移动棋子的一方输.

具体的移动棋子的规则如下：

1. 每次只能移动一个棋子

2. 棋子可以移动到水平或对角线8个方向上相邻的空格子中

如下图所示，白子可以移动到左、上、右、右下、下或左下的空格子中.

3. 棋子可以跳过水平或对角线8个方向上紧邻的对方的棋子，但必须能落在该方向上后续相邻的空格子上，且只能跳过一个对方棋子，被跳过的对方棋子立刻翻转为己方棋子.

如下面左图所示，白子可以跳过右、右下或下方的黑子. 如下面右图所示，棋子一次跳跃不能跳过多个对方的棋子

4. 每当移动己方棋子跳过对方一个棋子后，可以选择停止此轮行动或者继续按上述第3条规则跳过其他对方的棋子.

如下图所示，白子可以连续两次跳过黑子.

给出一个棋局以及接下来该谁行动，判断接下来行动的一方是否有必胜策略.

Input

包含不超过10000组测试数据.

每组测试数据的第一行包含一个整数，该整数为1表示接下来由黑方行动，为0表示接下来由白方行动.

接下来4行描述了棋局，其中

• “.”表示该格子没有棋子
• “#”表示该格子的棋子黑色面朝上
• “+”表示该格子的棋子白色面朝上

数据保证每个棋局均包含8个棋子且至少有一个“#”和一个“+”.

Output

如果接下来行动的一方有必胜策略输出1，否则输出0.

Sample

0
####
....
....
++++
1
.#+.
.+++
..+.
.#.+

0
1

Hint

Source

Author

Staginner