20118번 - 호반우가 길을 건너간 이유 스페셜 저지

문제

호반우 농장의 호반우들은 17세가 되면 농장의 미로처럼 생긴 길을 건너가는 풍습이 있다. 왜 그런 풍습이 만들어졌는지는 농부 존도 모른다. 호반우들은 길을 건너가고 싶으니까 건너갈 뿐이다.

농장의 미로는 격자 형태로 나타낼 수 있고 격자의 각 칸에는 양의 정수 하나가 적혀있다.

호반우들은 격자 제일 왼쪽 위에서 출발하여 오른쪽 아래에서 끝나는 경로로 이동한다.

이 때 한 번 방문했던 칸을 다시 방문해도 되며 현재 칸에서 가로 세로 대각선(8방향)으로 인접한 칸으로만 이동할 수 있다.

농부 존은 호반우들이 걸어가는 경로를 유심히 관찰하던 중 놀라운 사실을 발견했다. 바로 호반우들이 걸어가는 경로에 적혀있는 수들을 xor한 값은 항상 0이 된다는 사실이다.

더 자세하게는, 호반우들이 걸어가는 지점에 적힌 수를 a₁, a₂, ..., a_n 이라고 하면 a₁ ⊕ a₂ ⊕ ... ⊕a_n = 0 이다. (⊕는 xor을 나타내는 기호다.)

농부 존은 이러한 사실을 기반으로 호반우가 건너갈 길의 경로를 예측하려고 한다. 하지만 농부 존은 비트 연산에 약해서 경로를 예측하는 데 실패했다. 그를 도와 호반우가 갈 수 있는 길의 경로를 찾는 프로그램을 만들어주자!

호반우가 갈 수 있는 길이 여러가지 있을 경우 아무거나 출력한다.

또한 호반우는 최단거리로 이동하지 않아도 된다.

호반우가 항상 길을 건너갈 수 있음을 증명할 수 있다.

입력

첫 번째 줄에 정수 N, M이 주어집니다. (2 ≤ N, M ≤ 1000)

N은 격자의 세로 크기, M은 격자의 가로 크기를 나타냅니다.

두 번째 줄 부터 N+1번째 줄 까지는 격자에 적힌 수가 공백으로 구분되어 주어집니다. (1 ≤ a_ij ≤ 10⁹)

출력

첫 번째 줄에 호반우가 방문한 칸의 개수 K를 출력합니다. 이 때 K가 2×(N+M)을 초과한 경우 오답으로 처리합니다.

두 번째 줄 부터 K+1번째 줄 까지는 호반우가 방문한 경로의 좌표를 나타내는 정수 y, x를 공백으로 구분하여 출력합니다.

제한

노트

격자의 왼쪽 위가 0, 0 이고 오른쪽 밑이 N-1, M-1 입니다.

경로에는 시작 지점과 끝 지점이 포함되어야 합니다.