34566번 - Thinking Tiling 1 스페셜 저지

문제

세로 길이 $R,ドル 가로 길이 $C$의 직사각형 영역을 2ドル\times 3$ 크기의 직사각형 타일로 덮으려고 한다. 이때 두 타일이 겹치거나, 직사각형 영역 밖으로 나가거나, 덮이지 않은 틈이 생기지 않도록 직사각형 타일을 배치할 수 있는지 판별하고, 가능하다면 그러한 배치를 아무거나 하나 출력하시오. 타일은 회전할 수 있다. 사용한 타일의 개수를 최소화하거나 최대화할 필요는 없다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. (1ドル\le T\le 1\ 000$)

둘째 줄부터 $T$개의 줄에 걸쳐서, 각 테스트 케이스마다 정수 $R$과 $C$가 한 줄에 공백으로 구분되어 주어진다. (1ドル\le R,C\le 1\ 000$)

모든 테스트 케이스에서 $R\times C$의 합은 10ドル^6$을 초과하지 않는다.

출력

각 테스트 케이스마다 다음과 같이 출력한다.

• 조건을 충족하는 타일의 배치가 존재한다면, 첫째 줄에 타일의 개수 $n$을 먼저 출력하고, 둘째 줄부터 $n$개의 줄에 걸쳐 각 타일의 배치를 $type,ドル $r,ドル $c$의 순서로 공백으로 구분하여 출력한다. 타일을 가로로 길게 배치하고자 할 경우 $type$은 1이고, 세로로 길게 배치하면 2이다. $r$과 $c$는 그 타일의 맨 왼쪽 위 칸의 행 번호와 열 번호를 뜻하며, 직사각형 전체의 맨 왼쪽 위 칸은 1ドル$행 1ドル$열, 맨 아래 오른쪽 칸은 $R$행 $C$열이다.
• 그러한 배치가 존재하지 않는다면, 0을 출력한다.

제한

힌트