문제
관우가 요새 살이 쪄서 말을 타지 못하게 되자 적토마는 헛간 바깥으로 나갈 일이 없어 매우 심심해졌다. 적토마는 결국 재밌는 놀이를 만들기로 했다. 적토마는 헛간을 세로 n칸, 가로 m칸으로 나눠 놓고, 한 지점에서 시작해서 방문했던 지점은 다시 방문하지 않고 헛간의 모든 칸을 뛰어다니기로 했다. 단, 시작하는 지점과 끝나는 지점은 적토마 마음대로다.
적토마는 말이기 때문에, 체스의 나이트처럼 움직인다. 나이트는 위 그림과 같이 움직일 수 있다. 즉, 말 머리가 적토마에 해당한다면 그 주변에 있는 여덟 방향으로 뛰어다닐 수 있다. 그런데 적토마가 n과 m을 잘 선택하지 못한다면 혼자 놀기에 실패할 수도 있다. 적토마가 n과 m을 고르면, 놀 수 있는 방법 중 가장 번호가 작은 것을 출력해 주자.
입력
첫 번째 줄에 두 개의 자연수 n과 m이 공백으로 구분되어 입력된다. n과 m의 곱은 26을 넘지 않는다.
출력
만일 적토마가 n과 m을 잘못 골랐다면 첫 번째 줄에 -1을 출력한다. 그렇지 않다면 nm개의 줄에 걸쳐서 적토마가 뛰어다니게 될 칸의 위치를 차례로 출력한다. 칸의 위치를 출력할 때에는 행 번호, 열 번호의 순으로 출력한다. 즉, 위에서 네 번째, 왼쪽에서 세 번째 칸은 4 3으로 출력해야 한다.
답이 여러 가지 존재할 수 있다. 그러한 경우에는 시작점의 행 번호가 가장 작은 것을 출력한다. 그래도 답이 여러 가지 있다면 시작점의 열 번호를 기준으로 비교한다(그래도 같다면 두 번째 방문하게 되는 점부터 마지막 방문하게 되는 점까지 차례로 같은 방법으로 비교하도록 한다).
예제
3 4
1 1
2 3
3 1
1 2
2 4
3 2
1 3
2 1
3 3
1 4
2 2
3 4
로그인해야 코드를 작성할 수 있어요.