연아와 연재는 아래 그림과 같은 모양으로 보도블록이 깔린 지역에서 자주 놀곤 한다.
M 개의 행과 N 개의 열로 이루어진 M*N 크기의 보도블록은 2*M*N 개의 타일들로 구성되는데, 이 타일들은 짧은 변과 긴 변의 길이 비가 1:2 인 직사각형 모양으로 크기가 동일하고, 색은 흰색과 회색 두 종류가 있다.
M*N 크기의 보도블록에서 각 행은 위에서 아래로 1부터 M 까지 번호가 매겨져 있고, 각 열은 왼쪽에서 오른쪽으로 1부터 N 까지 번호가 매겨져 있다고 하자. i 행 j 열에는 색이 다른 두 타일이 정사각형 모양으로 맞붙어 배치되어 있는데, 배치된 모양은 i+j 의 값에 따라 다음 두 가지 중 하나이다.
연아와 연재는 이 보도블록에서 자주 게임을 하는데, 이 게임의 규칙은 간단하다.
먼저 보도블록의 크기를 정한다. 그런 다음 이 보도블록에 속한 타일 하나에서 출발하여 아래의 조건을 만족하면서 가능한 많은 개수의 타일을 밟고 지나서 다시 출발한 타일로 되돌아오는 게임이다.
예를 들어 그림 1(a)와 같이 2*3 크기의 보도블록에서는 다음과 같은 방법으로 12개의 타일을 모두 지날 수 있다.
(1,1,1) -> (1,1,0) -> (1,2,0) -> (1,2,1) -> (1,3,0) -> (1,3,1) -> (2,3,1) -> (2,3,0) -> (2,2,0) -> (2,2,1) -> (2,1,1) -> (2,1,0) -> (1,1,1)
보도블록의 크기 M*N 이 주어질 때 최대 몇 개의 타일을 지날 수 있는지, 그리고 어떤 순서로 타일을 지나야 최대 개수의 타일을 지나게 되는지를 알아내는 프로그램을 작성 하시오.
프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
입력 2 3 출력 12 1 1 1 1 1 0 1 2 0 1 2 1 1 3 0 1 3 1 2 3 1 2 3 0 2 2 0 2 2 1 2 1 1 2 1 0
출처:koi 2011 중등 지역 4 special judge:Fate대회 풀이