[HNOI2007]胜负一子

五子棋是一种流传广泛的棋类游戏。棋盘大小为 $15\times 15$ ，对弈双方分别执黑子和白子，黑方先行。棋子落下后不能被提起，即不存在挪子或吃子的情况。为简化问题，假设黑方不存在“禁手”。

当一方率先在横向、纵向、 $45$ 度斜线方向或 $135$ 度斜线方向形成连续的 $5$ 枚己方棋子时，该方获胜。

现在给定一盘轮到黑方落子的残局。双方从当前局面开始，轮流在空位落子，黑方先走，白方会采取最优策略阻止黑方获胜。一次“黑方步数”是指黑方落下一枚棋子。

请计算黑方保证获胜所需的最少黑方步数，并给出所有能够保证黑方在该最少步数内获胜的第一手落子位置。

输入格式

输入共 $15$ 行，每行包含 $15$ 个由空格分隔的整数。

第 $i$ 行、第 $j$ 列的整数记为 $v_{i,j}$ ：

$v_{i,j}=0$ 表示该位置为空；
$v_{i,j}=1$ 表示该位置有一枚黑子；
$v_{i,j}=2$ 表示该位置有一枚白子。

棋盘从左上角开始，按照从左到右、从上到下的顺序输入。即 $v_{1,1}$ 表示第 $1$ 行第 $1$ 列位置的状态， $v_{15,15}$ 表示第 $15$ 行第 $15$ 列位置的状态。

输出格式

第一行输出两个整数 $a$ 和 $b$ 。

其中， $a$ 表示从当前局面开始，在白方任意合法应对下，黑方保证获胜所需的最少黑方落子次数； $b$ 表示能够保证黑方恰好在 $a$ 步内获胜的不同第一手落子位置数。

接下来 $b$ 行，每行输出两个整数 $i$ 和 $j$ ，表示一种满足条件的第一手落子位置，即第 $i$ 行、第 $j$ 列。

所有位置按照 $15i+j$ 的值从小到大排列。

样例输入

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 2 0 2 0 0 0 0 0
0 0 0 0 0 0 2 1 1 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 1 0 0 0 0 0
0 0 0 0 0 0 2 1 1 1 1 2 0 0 0
0 0 0 0 0 0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 2 2 0 1 1 0 2 0 0
0 0 0 0 0 0 0 0 0 2 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出

数据范围

棋盘大小为 $15\times 15$ ；
输入保证当前局面尚未分出胜负，且轮到黑方落子；
所有非空棋子的位置互不冲突；
输入保证黑方存在强制获胜策略，并且在白方最优应对下，黑方至多落子 $8$ 次即可获胜。

来源与许可

本题为 HNOI 2007 试题「胜负一子」，题面与测试数据整理自 BZOJ。

样例 1

输入

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 2 0 2 0 0 0 0 0
0 0 0 0 0 0 2 1 1 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 1 0 0 0 0 0
0 0 0 0 0 0 2 1 1 1 1 2 0 0 0
0 0 0 0 0 0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 2 2 0 1 1 0 2 0 0
0 0 0 0 0 0 0 0 0 2 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

输出