4×4 격자판에 1에서 16까지 정수 번호 가 매겨진 16개 타일이 임의로 놓여져 있다. 타일을 움직여 그림 1과 같이 타일을 놓이게 하려고 한다.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

그림 1

타일을 움직이는 방법은 하나의 행(가로줄)을 오른쪽으로 원하는 칸 수만큼 순환 적으로 움직이거나, 하나의 열(세로줄)을 원하는 칸 수만큼 아래쪽으로 순환적으로 움직이는 것이다.

그림 2는 그림 1의 2번 째 행을 오른쪽으로 2칸 움직인 것이다. 그림 1의 2번째 행의 오른쪽 끝에 있는 7 번 타일과 8번 타일이 오른쪽 경계를 넘어가서 왼쪽 끝으로 옮겨갔다.

1	2	3	4
7	8	5	6
9	10	11	12
13	14	15	16

그림 2

그림 3은 그림 2의 3번째 열을 아래쪽으로 1칸 움직인 것이다. 그림 2의 3번째 열의 가장 아래에 있는 15번 타일이 가장 위쪽으로 옮겨갔다.

1	2	15	4
7	8	3	6
9	10	5	12
13	14	11	16

그림 3

1에서 16까지 번호가 매겨진 타일이 임의로 놓여져 있을 때 그림 1과 같이 타일이 놓일 수 있도록 타일을 움직이는 순서를 출력하는 프로그램을 작성하시오. 여기서 움직이는 횟수는 최소로 하여야 한다.

입력

출력

• 첫 번째 줄에는 움직이는 횟수를,
• 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이 때,
  • 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 한 줄에 출력한다.
  • 그리고 격자판의 i 번째 열을 k칸 움직였다면 정수 2와 i와 k를 빈칸을 사이에 두고 한 줄에 출력한다.
  여기서 i는 1 이상 4 이하, k는 1 이상 3 이하의 정수이다.

입출력 예

입력

1 2 15 4
7 8 3 6
9 10 5 12
13 14 11 16

출력

2
2 3 3
1 2 2

주의 사항

출처: 제26회 한국정보올림피아드 (2009.7.17) 초등부 문제 2