描述

龙猫要进行一次旅行。

具体地，龙猫旅行的地点可以视作一个 N\times NN×N 的网格。网格中除 (N,N)(N,N) 外的每个位置都有一个路标，用一个数字表示。设现在龙猫在网格 (x,y)(x,y) 上，那么：

路标为 11：下一步他应该走到 (x-1,y)(x−1,y)（即，往上走一格）； 路标为 22：下一步他应该走到 (x+1,y)(x+1,y)（即，往下走一格）； 路标为 33：下一步他应该走到 (x,y-1)(x,y−1)（即，往左走一格）； 路标为 44：下一步他应该走到 (x,y+1)(x,y+1)（即，往右走一格）。 最开始时龙猫在 (1,1)(1,1) 处，请输出他从 (1,1)(1,1) 走到 (N,N)(N,N) 的路径。如果龙猫永远走不到 (N,N)(N,N)，输出-1。

保证路标不会指向地图外的地方，即，按照路标行走，龙猫不可能走到 (x,y)(x,y)，其中 x,yx,y 满足 x<1x<1 或 x>Nx>N 或 y<1y<1 或 y>Ny>N。

输入 第一行一个正整数 NN；

接下来 NN 行，每行 NN 个在范围 [1,4][1,4] 内的正整数，表示每个点的路标。

特别地，(N,N)(N,N) 处的输入为 00。

输出 第一行一个整数，如果龙猫可以从 (1,1)(1,1) 到 (N,N)(N,N)，那么按顺序输出龙猫到达终点需要经过的点的数量 KK（包括 (1,1)(1,1) 和 (N,N)(N,N)），否则输出-1。

如果可以走到终点，那么接下来 KK 行，每行两个正整数 (x,y)(x,y)，第 ii 行表示第 ii 个经过的点。

输入样例 1

2 2 3 4 0 输出样例 1

3 1 1 2 1 2 2 输入样例 2

3 4 2 3 1 3 2 4 3 0 输出样例 2

-1 提示

样例 #1 解释：

龙猫将按以下的步骤完成旅行：

初始时他在 (1,1)(1,1)，路标为 22，他应该往下走到 (2,1)(2,1)； (2,1)(2,1) 处路标为 44，应该往右走到 (2,2)(2,2)； 此时已经到达了终点 (2,2)(2,2)。 总共经过了 33 个点。

样例 #2 解释：

显然龙猫会一直在 (1,1),(1,2),(2,2),(2,1)(1,1),(1,2),(2,2),(2,1) 间一直绕圈，永远不可能到达终点。

数据范围：

对于 10%10% 的数据，1\le N\le 101≤N≤10；

对于 100%100% 的数据，1\le N\le 601≤N≤60，所有路标都是范围在 [1,4][1,4] 之间的正整数，且保证路标不会指向地图外的地方，即，按照路标行走，龙猫不可能走到 (x,y)(x,y)，其中 x,yx,y 满足 x<1x<1 或 x>Nx>N 或 y<1y<1 或 y>Ny>N。