Quento는 Q42에서 만든 게임이다. 이 게임의 게임판은 항상 3×3 크기이며, 오른쪽 그림과 같이 검정색 칸에는 숫자, 흰색 칸에는 +또는 -가 적혀져 있다.</p>

게임판의 상단에는 만들어야하는 숫자 N과 사용해야 하는 숫자의 개수 M이 주어진다. 이제 숫자에서 스와이프를 시작해 +/-로 이동한 다음, 다시 숫자로 스와이프를 하고, 이런식으로 숫자를 M개 지났을 때, 결과가 N이 되어야 한다. 이미 방문한 칸은 재방문 할 수 없으며, 다시 지나가는 것도 불가능하다.

예를 들어, 7을 숫자 2개를 이용해서 만들려면, 4+3, 9-2는 가능하다. 하지만, 5+3-1은 숫자 3개를 이용했기 때문에 불가능하다.

N과 M, 그리고 게임판에 쓰여 있는 숫자와 +/-가 주어진다. 이때, 숫자 M개를 이용해서 N을 만드는 방법을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 45, 2 ≤ M ≤ 5) 둘째 줄부터 3개의 줄에 걸쳐 게임판에 써잇는 숫자와 +/-가 주어진다. 숫자는 항상 한자리 숫자이고, 0이 아니다.

출력 형식

M개의 숫자를 이용해서 N을 만들 수 있으면, 첫째 줄에 1을 출력하고, 없는 경우에는 0을 출력한다. 그 다음, 숫자를 만들 수 있는 경우에는 방문한 칸을 총 2*M-1개 줄에 걸쳐서 출력한다. 가장 왼쪽 윗칸의 좌표는 (0, 0), 왼쪽 아랫칸의 좌표는 (2, 0), 오른쪽 윗칸의 좌표는 (0, 2), 오른쪽 아랫칸의 좌표는 (2, 2)이다.</p>

가능한 방법이 여러 가지인 경우 아무거나 하나만 출력한다.

예제 입력 1

11 2
6+5
-3-
8+4

예제 출력 1

1
0 0
0 1
0 2

예제 입력 2

1 3
6+5
-3-
8+4

예제 출력 2

1
2 2
2 1
1 1
1 0
0 0

예제 입력 3

15 3
6+5
-3-
8+4

예제 출력 3

0

힌트

이 게임은 다운받아서 직접해 볼 수 있다.</p>

http://quento.com/