#include <cstdio>
#include <utility>
#include <cctype>
#include <vector>
using namespace std;

#ifdef __linux
#define _U(s) s##_unlocked
#else
#define _U(s) _##s##_nolock
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#define gcu _U(getchar)
#define pcu _U(putchar)
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;char c;while(isspace(c = gcu()));do{s+=c;}while(c=gcu(),c!=' '&&c!='\n'&&c!=EOF);return s;}
#define _S
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;while(isspace(c = gcu()));if(c=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
#ifdef _S
_SCAN(string &o) {int c{gcu()};if(c==EOF)return false;else{ungetc(c,stdin);string t=move(in);o=t;return true;}}
#endif
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _S
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
	_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H &&h, T... t){out(h);out(t...);}
template <typename... T> _OUTL(T... t){out(t...);outl();}
struct range{
	int e,b=0,s=1;range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it{int v,s; it(int _v,int _s):v(_v),s(_s){} operator int()const{return v;} operator int&(){return v;}int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin(){return {b,s};} it end(){return {e,s};}};
#define times(i,n) for(int i=n;i;i--)

template <typename T>
using V = vector<T>;

int main() {
	for (int n; (n = in);) {
		int m {(int) in - 1}, s {(int) in - 1}, d {in};
		V<V<bool>> a(d, V<bool>(n + 1)), memo = a;
		auto move = [&] (int x, int y) {
			return a[y][x] ? x - 1 : a[y][x + 1] ? x + 1 : x;
		};
		auto is_start = [&] (int x, int y) {
			for (int i: range(y, -1, -1)) {
				if (memo[i][x])
					return false;
				memo[i][x] = true;
				x = move(x, i);
			}
			return x == m;
		};
		auto add = [&] (int x, int y) {
			return !a[y][x - 1] && !a[y][x] && !a[y][x + 1];
		};

		for (auto &i: a) {
			for (int j: range(1, n))
				i[j] = gcu() - '0';
			gcu();
		}
		V<int> v(d);
		int c {s};
		for (int i: range(d - 1, -1, -1)) {
			v[i] = c;
			c = move(c, i);
		}
		if (c == m)
			outl(0);
		else
			[&] {
				for (int y: range(d)) {
					int x {v[y]};
					if (x > 0 && add(x, y) && is_start(x - 1, y - 1)) {
						outl(y + 1, ' ', x);
						return;
					} else if ((x < n - 1 && add(x + 1, y) && is_start(x + 1, y - 1))) {
						outl(y + 1, ' ', x + 1);
						return;
					}
				}
				outl(1);
			}();
	}
}

### Prompt

Construct a Cpp code solution to the problem outlined:

There are n vertical lines in the Amidakuji. This Amidakuji meets the following conditions.

* Draw a horizontal line right next to it. Do not pull diagonally.
* Horizontal lines always connect adjacent vertical lines. In other words, the horizontal line does not cross the vertical line.
* For any vertical line, horizontal lines will not appear at the same time on the left and right from the same point. That is, the horizontal line does not cross the vertical line.
* There is only one hit.



The figure below shows an example of Amidakuji when n = 5. The numbers on the top represent the vertical line numbers (1, 2, 3, 4, 5 from the left). ☆ is a hit.

<image>


Create a program that reads the number of vertical lines n, the number m of the selected vertical line, the location of the Amidakuji hit, and the presence or absence of horizontal lines in each row, and outputs a judgment as to whether or not the hit can be reached. However, only one horizontal line can be added at any position in the given Amidakuji (it is not necessary to add it). The Amidakuji after adding one horizontal line must also meet the above conditions.



Input

Given multiple datasets. Each dataset is as follows:

The number of vertical lines n (1 <n ≤ 10) is written on the first line.
On the second line, the number m (1 ≤ m ≤ n) of the selected vertical line is written.
On the third line, the number of the hit place (☆ in the figure) is written counting from the left.
On the 4th line, the number of stages d (1 ≤ d ≤ 30) of Amidakuji is written.
From the 5th line onward, n-1 numbers are lined up in order from the top of the Amidakuji, with 1 being the horizontal line between each vertical line and 0 being the absence, as in the sequence of numbers corresponding to the figure. is.


The input ends on a line with a single 0.

Output

For each dataset, output the following values ​​depending on whether you can reach the hit from the selected vertical line number m.

* Output 0 if you can reach the hit without drawing a horizontal line.
* If you can reach the hit by drawing one horizontal line, output the position of the horizontal line closest to the starting side (upper in the figure). Please output the number of steps (see the figure) counting from the departure side and the number of vertical lines counting from the left to draw the horizontal line to the right, separated by a half-width space.
* If you cannot reach the hit even if you draw one horizontal line, output 1.

Example

Input

5
2
3
9
1010
1001
0100
1001
0010
1000
0100
0101
1010
0


Output

6 4

### Response

```cpp
#include <cstdio>
#include <utility>
#include <cctype>
#include <vector>
using namespace std;

#ifdef __linux
#define _U(s) s##_unlocked
#else
#define _U(s) _##s##_nolock
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#define gcu _U(getchar)
#define pcu _U(putchar)
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;char c;while(isspace(c = gcu()));do{s+=c;}while(c=gcu(),c!=' '&&c!='\n'&&c!=EOF);return s;}
#define _S
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;while(isspace(c = gcu()));if(c=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
#ifdef _S
_SCAN(string &o) {int c{gcu()};if(c==EOF)return false;else{ungetc(c,stdin);string t=move(in);o=t;return true;}}
#endif
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _S
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
	_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H &&h, T... t){out(h);out(t...);}
template <typename... T> _OUTL(T... t){out(t...);outl();}
struct range{
	int e,b=0,s=1;range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it{int v,s; it(int _v,int _s):v(_v),s(_s){} operator int()const{return v;} operator int&(){return v;}int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin(){return {b,s};} it end(){return {e,s};}};
#define times(i,n) for(int i=n;i;i--)

template <typename T>
using V = vector<T>;

int main() {
	for (int n; (n = in);) {
		int m {(int) in - 1}, s {(int) in - 1}, d {in};
		V<V<bool>> a(d, V<bool>(n + 1)), memo = a;
		auto move = [&] (int x, int y) {
			return a[y][x] ? x - 1 : a[y][x + 1] ? x + 1 : x;
		};
		auto is_start = [&] (int x, int y) {
			for (int i: range(y, -1, -1)) {
				if (memo[i][x])
					return false;
				memo[i][x] = true;
				x = move(x, i);
			}
			return x == m;
		};
		auto add = [&] (int x, int y) {
			return !a[y][x - 1] && !a[y][x] && !a[y][x + 1];
		};

		for (auto &i: a) {
			for (int j: range(1, n))
				i[j] = gcu() - '0';
			gcu();
		}
		V<int> v(d);
		int c {s};
		for (int i: range(d - 1, -1, -1)) {
			v[i] = c;
			c = move(c, i);
		}
		if (c == m)
			outl(0);
		else
			[&] {
				for (int y: range(d)) {
					int x {v[y]};
					if (x > 0 && add(x, y) && is_start(x - 1, y - 1)) {
						outl(y + 1, ' ', x);
						return;
					} else if ((x < n - 1 && add(x + 1, y) && is_start(x + 1, y - 1))) {
						outl(y + 1, ' ', x + 1);
						return;
					}
				}
				outl(1);
			}();
	}
}

```