柒某人参加了一个密室找宝藏的冒险活动,密室是一个巨大的 n 行 m 列的矩阵。柒某人的视力非常好,她能从密室的一端沿直线看到密室的另一端(但她只能看八个方向——东北,东,东南,南,西南……),而且她跑得非常快,跑一步(向上、下、左、右移动一格)只需要 1s。但密室是不透光的,而且,要破坏密室的墙也不容易,所以柒某人决定绕到一个能够看到宝藏的地方。现在,柒某人希望你能帮她确定最短需要多长时间才能得到宝藏。
第一行为 2 个数 N,M 表示密室的规模(N 为高,M 为宽)
接下来是 N×M 的密室,O 表示空地,X 表示墙。
最后是多对数据,分别是宝藏坐标及柒某人的坐标。
根据每对数据,计算柒某人拿到宝藏的最短时间,每对一行。如果有意难为柒某人,用墙将宝藏包围了起来,输出 Impossible。
3 4OXXOXXOOXOOO3 2 2 43 3 1 1
1Impossible
1<=n,m<=1000