#1132. 希蒙的旅行

希蒙的旅行

希蒙的旅行

题目描述

赛码家园面积辽阔。其地图可以被划分为 nnmm 列。用 (i,j)(i,j) 来表示第 ii 行第 jj 列的位置。

希蒙的旅行开始了,他将从 (Sx,Sy)(S_x,S_y) 出发。在每一个 (i,j)(i,j) 位置有着任务指引,告诉希蒙她下一步应该前往第 ii 行第 jj 列的位置,或者是结束旅行。

请你依次输出希蒙的旅行到达的位置信息,数据保证旅行能够在有限步内结束。

输入格式

输入的第一行为四个整数 m,n,Sx,Sym,n,S_x,S_y,分别代表列数、行数和开始的坐标。

接下来 nn 行,每行 2m2m 个整数。第 ii 行的第 2j12\cdot j-1 和第 2j2 \cdot j 个数为第 ii 行第 jj 列的“任务指引”。若两个数均为 00,则代表结束旅行。这些数均为 0max{n,m}0 \sim \max \{n, m\} 范围内的整数。

输出格式

输出若干行,每行两个数 x,yx,y,由空格分开,代表希蒙的旅行路径经过了 (x,y)(x,y)

样例 #1

样例输入 #1

3 3 1 1
1 2 1 3 2 1
2 2 0 0 2 3
3 2 3 3 1 1

样例输出 #1

1 1
1 2
1 3
2 1
2 2

提示

样例 1 解释

希蒙从 (1,1)(1,1) 出发,依次经过 (1,2),(1,3),(2,1)(1,2),(1,3),(2,1),在 (2,2)(2,2) 终止旅行。

数据规模与约定

对于 30%30\% 的测试数据,n=mn = m; 对于另外 30%30\% 的测试数据,Sx=Sy=1S_x=S_y=1; 对于 100%100\% 的测试数据,1n,m1031 \le n,m \le 10^31Sxn1 \le S_x \le n1Sym1 \le S_y \le m