Page not loading? Try clicking here.
Placeholder

#8672

직사각형 게임 2s 1024MB

Problems

ecode는 N개의 행과 M개의 열로 이루어진 N×M 크기의 격자 모양 숫자 보드에 존재하는 모든 a×b 크기의 직사각형에 대하여 포함되는 수들의 합이 그 어떤 경우에도 짝수가 되지 않는 (a,b) 쌍을 구하는 게임을 하고 있다.

ecode는 (a,b) 쌍을 가능한 한 많이 찾아 게임에서 이기고 싶다. ecode를 위해 격자 모양 숫자 보드에 존재하는 모든 (a,b) 쌍을 출력하는 프로그램을 작성하시오.


Input

첫 번째 줄에 N, M이 공백으로 구분되어 주어진다. (1≤N,M≤2,000)

두 번째 줄부터 N개의 줄에 걸쳐 9 이하의 양의 정수로 이루어진 N×M 크기의 격자 모양 숫자 보드가 주어진다.


Output

첫 번째 줄에 (a,b) 쌍의 개수 K를 출력한다.

두 번째 줄부터 N개의 줄에 걸쳐 9 이하의 양의 정수로 이루어진 정수 M개가 공백으로 구분하여 주어진다. i번째 줄의 j번째 수는 격자 모양 숫자 보드의 i번째 행 j번째 열에 적힌 수를 의미한다. 정답은 a의 오름차순으로 출력하며, a가 같은 경우 b의 오름차순으로 출력한다. (1≤a≤N;1≤b≤M)


Example #1

4 3
2 1 7
5 8 3
3 9 1
1 5 4
3
3 3
4 1
4 3

Example #2

3 4
3 6 9 1
8 5 2 3
3 1 5 8
1
2 4

Example #3

1 1
2
0


Source

제 3회 디미고 프로그래밍 챌린지

You must sign in to write code.