题目描述

2019年的暑假，比以往来得更晚一些。因为要准备NOIP全国联赛，你刚放假就被爸妈叫去上信息学课程。好不容易等到课程结束，在冲刺班开始之前，你爸妈决定带你去东部华侨城玩一趟，让你放松一下自己。

在华侨城有一个迷宫，迷宫很大，一般人要走很久才能出来。看着迷宫里的人跌跌撞撞地找不到路，作为学过算法的OICoder学子，你的嘴角浮现出一丝不屑的笑。你知道有一种好方法，可以让他们快速地走出迷宫。那就是先拿到迷宫的平面图，然后求出从起点到终点的最少步数以及对应的路径。沿着最短路径走，就可以又快又轻松地走出迷宫了。

想到这里，你用“毕莘牌”无人机扫描了一遍迷宫，得到一幅迷宫平面图，用一个 N×M 的矩阵表示。在该矩阵中，1代表起点，2代表终点，3代表墙壁，4代表可走的路。从起点开始，每一步，你可以选择往上、往下、往左或往右移动，但不可以移动到墙壁，也不可以在除终点外的其他位置离开迷宫。有了这幅图，走迷宫就是小意思啦！

请你根据该迷宫地图，求出从起点到终点的最少步数，以及该最少步数对应的路径（路径包含起点和终点）。输入数据保证有且只有一条可以走出迷宫的最短路径。 请注意：只要到达了终点，就算走出了迷宫。若最少步数是偶数，则需要输出具体路径。若最少步数是奇数，则不需要输出具体路径。

输入格式

第1行，输入 N 和 M，代表矩阵具有 N 行 M 列。

第2行到第 N+1 行，依次输入矩阵第1行到第 N 行的数据。

输出格式

第1行输出走出该迷宫需要的最少步数。若最少步数是偶数，从第2行开始，从前往后输出路径中的每一个位置。一个位置占一行，用 (x,y) 表示，其中 x 表示该位置在矩阵中的行下标，y 表示该位置在矩阵中的列下标。矩阵的行、列下标均从1开始编号，具体见样例2。

5 5
1 3 3 4 3
4 4 3 4 3
3 4 4 4 4
3 3 3 4 3
3 3 3 2 3

7

5 5
1 3 3 4 3
4 4 3 4 3
3 4 4 4 4
3 3 3 4 3
3 3 3 4 2

8
(1,1)
(2,1)
(2,2)
(3,2)
(3,3)
(3,4)
(4,4)
(5,4)
(5,5)

样例说明

样例1走出迷宫的最少步数是奇数，不需要输出具体路径。 样例2走出迷宫的最少步数是偶数，需要输出具体路径。

数据范围

3≤N,M≤1000 。